[Overview] [Previous] [Next]

Primitive Regular Expressions

A regular expression can be used to define a language. A regular expression represents a "pattern;" strings that match the pattern are in the language, strings that do not match the pattern are not in the language.

As usual, the strings are over some alphabet sigma.

Important! The following are primitive regular expressions:

Thus, if |sigma| = n, then there are n+2 primitive regular expressions defined over sigma.

Here are the languages defined by the primitive regular expressions:

Copyright 1996 by David Matuszek
Last modified Feb 4, 1996