Example of Regular Expression

Ex. 6:
Find a regular expression corresponding to the language of all strings over the alphabet { a, b } that contain no more than one occurence of the string aa.

Solution:
If there is one substring aa in a string of the language, then that aa can be followed by any number of b. If an a comes after that aa, then that a must be preceded by b because otherwise there are two occurences of aa. Hence any string that follows aa is represented by ( b + ba )*. On the other hand if an a precedes the aa, then it must be followed by b. Hence a string preceding the aa can be represented by ( b + ab )*. Hence if a string of the language contains aa then it corresponds to the regular expression ( b + ab )*aa( b + ba )* .

If there is no aa but at least one a exists in a string of the language, then applying the same argument as for aa to a, ( b + ab )*a( b + ba )* is obtained as a regular expression corresponding to such strings.

If there may not be any a in a string of the language, then applying the same argument as for aa to , ( b + ab )*( b + ba )* is obtained as a regular expression corresponding to such strings.
Altogether ( b + ab )*( + a + aa )( b + ba )* is a regular expression for the language.

Examples of regular expression and regular languages

So far, we have discussed several important formal definitions. Now we will see some good examples of them. We will discuss other important definitions time to time.

Examples of regular expression and regular languages corresponding to them

•( a + b )2 corresponds to the language {aa, ab, ba, bb}, that is the set of strings of length 2 over the alphabet {a, b}.

In general ( a + b )k corresponds to the set of strings of length k over the alphabet {a, b}. ( a + b )* corresponds to the set of all strings over the alphabet {a, b}.

•a*b* corresponds to the set of strings consisting of zero or more a's followed by zero or more b's.

•a*b+a* corresponds to the set of strings consisting of zero or more a's followed by one or more b's followed by zero or more a's.

•( ab )+ corresponds to the language {ab, abab, ababab, ... }, that is, the set of strings of repeated ab's.


Note:
A regular expression is not unique for a language. That is, a regular language, in general, corresponds to more than one regular expression. For example (a + b)* and ( a*b* )* correspond to the set of all strings over the alphabet {a, b}.


Definition of Equality of Regular Expressions

Regular expressions are equal if and only if they correspond to the same language.

Thus for example (a + b)* = (a*b*)*, because they both represent the language of all strings over the alphabet {a, b}.

In general, it is not easy to see by inspection whether or not two regular expressions are equal.