# Nfas To Regular Expression

S**olution**

(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*)*