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