Regular Expression

Regular expressions define formal languages as sets of strings over a finite alphabet. Let  denote a selected alphabet. Then  is a regular expression that denotes the empty set and  is a regular expression that denotes the set containing the empty string as its only element.

If , then  is a regular expression that denotes the set whose only element is string . If  and  are regular expressions denoting sets  and , then

1.  is a regular expression denoting the set , where  denotes the union.

2.  is a regular expression denoting the set of all concatenations of  and , where  and .

3.  is a regular expression denoting closure of , that is, the set of zero or more concatenations of strings from 

The sets defined by regular expressions are called regular sets, and a set is regular iff it is defined by a right linear grammar.

REFERENCES

Aho, A. V. and Ullman J. D. Theory of Parsing, Translation and Compiling, Vol. 1. Englewood Cliffs, NJ: Prentice Hall, 1972.

Aho, A. V. and Ullman J. D. Theory of Parsing, Translation and Compiling, Vol. 2. Englewood Cliffs, NJ: Prentice Hall, 1972.