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.

More examples

Ex. 5:
Describe as simply as possible in English the language corresponding to the regular expression (( a + b )3)*( #+ a + b ) .

Solution:
(( a + b )3) represents the strings of length 3. Hence (( a + b )3)* represents the strings of length a multiple of 3. Since (( a + b )3)*( a + b ) represents the strings of length 3n + 1, where n is a natural number, the given regular expression represents the strings of length 3n and 3n + 1, where n is a natural number.

Examples of Regular Grammars and Regular Expressions

Ex. 2:
Find a regular expression corresponding to the language of all strings over the alphabet { a, b } that contain exactly two a's.

Solution:
A string in this language must have at least two a's. Since any string of b's can be placed in front of the first a, behind the second a and between the two a's, and since an arbitrasry string of b's can be represented by the regular expression b*, b*a b*a b* is a regular expression for this language.


Ex. 3:
Find a regular expression corresponding to the language of all strings over the alphabet { a, b } that do not end with ab.

Solution:
Any string in a language over { a , b } must end in a or b. Hence if a string does not end with ab then it ends with a or if it ends with b the last b must be preceded by a symbol b. Since it can have any string in front of the last a or bb, ( a + b )*( a + bb ) 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.