Let S² = {a, b}. Then the following are regular languages (RLs) using the base case in the recursive definition.
|
Æ |
E = {e} |
A = {a} |
B = {b} |
The concatenation operation allows us to state that longer strings also constitute RLs, for example:
|
A^A = {aa} |
A^B = {ab} |
B^A = {ba} |
B^B = {bb} |
The union operation allows us to state that sets with more than one string in them are RLs, but does not create new strings. For example, given the RLs already defined, union allows us to conclude that the following sets are also RLs.
|
E|A = {e, a} |
E|B = {e, b} |
A|B = {a, b} |
E|A^A = {e, aa} |
|
E|A^B = {e, ab} |
E|B^A = {e, ba} |
E|B^B = {e, bb} |
A|A^A = {a, aa} |
|
A|A^B = {a, ab} |
A|B^A = {a, ba} |
A|B^B = {a, bb} |
B|A^A = {b, aa} |
|
B|A^B = {b, ab} |
B|B^A = {b, ba} |
B|B^B = {b, bb} |
A^A|A^B = {aa, ab} |
|
A^A|B^A = {aa. ba} |
A^A|B^B = {aa, bb} |
A^B|B^A = {ab, ba} |
A^B|B^B = {ab, bb} |
|
B^A|B^B = {ba, bb} |
|
|
|
Once we have an RL with more than one non-empty member, concatenation by itself can form new RLs with even more members. For example A|B^A|B = {aa, ab, ba, bb}.
This process of combining concatenation with union can continue without limit, recursively enumerating all and only all the finite RLs over S². To obtain infinite RLs including those with infinite complements, unbounded repetition must be used.