(d) all strings which contain no runs of a’s of length greater than two.
(e) all strings in which all runs of a’s have lengths that are multiples of
three.
Solu tion
(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
(
) (
) (
)
λ
λ
λ
+
+
+
a
a
a
Now we want to allow arbitrary strings not containing a’s at the
places marked by X’s:
X
a X
a X
a X
(
) (
) (
)
λ
λ
λ
+
+
+
Therefore we put (b + c)
* for each X.
(
) (
) (
) (
) (
) (
) (
)
*
*
*
*
b c
a b c
a b c
a b c
+
+
+
+
+
+
+
λ
λ
λ
(c) All strings which contain at least one occurrence of each symbol
in Σ:
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:
(
) (
) (
) (
)
(
) (
*
*
*
*
*
a b c a a b c b a b c c a b c
a b c a a b
+ +
+ +
+ +
+ +
+
+ +
+ + c c a b c b a b c
a b c b a b c a a b c c
) (
) (
)
(
) (
) (
) (
*
*
*
*
*
*
+ +
+ +
+
+ +
+ +
+ +
a b c
a b c b a b c c a b c a a b c
a b c
+ +
+
+ +
+ +
+ +
+ +
+
+ +
)
(
) (
) (
) (
)
(
*
*
*
*
*
) (
) (
) (
)
(
) (
) (
*
*
*
*
*
*
c a b c a a b c b a b c
a b c c a b c b a
+ +
+ +
+ +
+
+ +
+ +
+ +
+ +
b c a a b c
) (
)
*
*
(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
a aa b c
+
+ +
+
λ
86
Theory of Automata, Formal Languages and Computation