But if we want to repeat this, we have to ensure to have least one
non-a between repetitions:
(
) (
)(
) ((
)(
) (
)(
) )
*
*
*
* *
b c
a aa b c
b c b c
a aa b c
+
+ +
+
+
+
+ +
+
λ
λ
(e) All strings in which all runs of a’s have lengths that are multiples
of three:
(
)
*
aaa b c
+ +
Ì Exam ple 1.4.6: Find regular expressions over Σ = { , }
a b for the
language defined as follows:
(a) L
a b m
m m
1
0
=
>
{
:
}
(b) L
b ab m
n
m
n
2
0
0
=
>
>
{
:
,
}
(c) L
a b m
n
m m
3
0
0
=
>
>
{
,
,
}
Solu tion
(a) Given L
a b m
m m
1
0
=
>
{
:
},
L 1 has those words beginning with one or more a’s followed by
one or more b’s.
Therefore the regular expression is
aa bb
a ab b
*
*
*
*
( )
or
(b) Given L
b ab m
n
m
n
2
0
0
=
>
>
{
:
,
}. This language has those words
w whose letters are all b except for one ‘a’ that is not the first or
last letter of w.
Therefore the regular expression is
bb
* abb
*
(c) Given L
a b m
m m
3
0
=
>
{
,
}.
There is no regular expression for this beginning as L 3 is not
regular.
Ì Exam ple 1.4.7: Determine all strings in L a b b a ab
((
) (
) )
*
*
+
+
of
length less than four.
Solu tion
b, ab, bb, ba, aab, abb, bab, bbb, baa, bba, aba
Ì Exam ple 1.4.8: Find the regular expressions for the languages defined
by
DFA and NFA
87