ASL STEM

Definition

A regular expression in a finite alphabet A is defined recursively. Base case: A symbol in A or L (lambda). Recursive case: if x and y are regular expressions then so are (xy), (xUy), and x*. Each regular expression defines a set of strings. A member a of A defines the set {a} and the symbol L defines {}, the empty set. The set defined by (xy) is the set of strings formed by concatenating a string from the set defined by x with a string from the set defined by y. The set defined by (xUy) is the union of the set defined by x and the set defined by y. Finally, the set defined by x* is the set of strings formed by concatenating any number of strings from the set defined by x together. One special case is concatenating zero strings from the set defined by x together. This means L is in the set defined by x* for any x. The parentheses are often dropped using the normal precedence of concatenation and union.

Example

(00 U 11)* defines the set {L, 00, 11, 0000, 0011, 1100, 1111, ...}