SKEDSOFT

Solution

(a)    R.E = (b c)* a (b c)* [for all strings containing exact one a]

(b)    All strings containing no more than three a’s: We can describe the string containing zero, one, two or three a’s (and nothing else) as

(l a) (l a) (l a)

Now we want to allow arbitrary strings not containing a’s at the places marked by X’s:

X (l a)X (l a)X (l a)X

Therefore we put (b c)* for each X.

(b c)* (l a) (b c)* (l a) (b c)* (l a) (b c)*

(c)    All strings which contain at least one occurrence of each symbol in S:

Here we cannot assume the symbols are in any particular order. We have no way of saying “in any order’, so we have to list the possible orders:

abc acb bac bca cab cba

Let us put X in every place where we want to allow an arbitrary string:

XaXbXcX XaXcXbX XbXaXcX XbXcXaX XcXaXbX XcXbXaX

Finally, we replace all X’s with (a b c)* to get the final regular expression:

(d)    All strings which contain no runs of a’s of length greater than two: An expression containing no a, one a, or one aa:

(b c)* (l a aa)(b c)*

But if we want to repeat this, we have to ensure to have least one non-a between repetitions:

(b c)* (l a aa)(b c)* ((b c)(b c)* (l a aa)(b c)* )*

(e)       All strings in which all runs of a’s have lengths that are multiples of three:

(aaa b c)*