LING 501, Fall 2004: Building regular languages with concatenation and union

Revised September 4, 2004 to correct the claim of what concatenation and union of regular languages can accomplish.

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.