Ì Exam ple 1.4.3: Obtain the regular expressions for the languages given
by
(a) L
a b
n
m
n
m
1
2
2
1
0
0
=
≥
≥
+
{
|
,
}
(b) L
a bb aa abb ba bbb
2 = { , , ,
, ,
,
}
KK
(c) L
w
w
3
01
= ∈
{
{ , } |
*
has no pair of consecutive zeros}
(d) L 4 = {strings of 0’s and 1’s ending in 00}
Solu tion
(a) L
a b
n
m
n
m
1
2
2
1
0
0
=
≥
≥
+
{
|
,
} denotes the regular expression
(aa)
* (bb)
* b
(b) The
regular
expression
for
the
language
L
a bb aa abb ba
2 = { , , ,
, , bbb,
}
KK
(a + b)
* (a + bb)
(c) The regular expression for the language L
w
w
3
01
= ∈
{
{ , } |
*
has no
pair of consecutive zeros} is given by
(
) (
)
*
* *
1 011
0 + +
λ 1 0
* (
)
+ λ
(d) The regular expression for the language L 4 = {strings of 0’s and
1’s beginning with 0 and ending with 1} is given by
0 (0 + 1)
* 1
Ì Exam ple 1.4.4: Describe the set represented by the regular expression
(aa + b)
* (bb + a)
*
Solu tion
The given regular expression is
(
) (
)
*
*
aa b bb a
+
+
.
The English language description is as follows: “The set of all the strings of the
form uv where a’s are in pairs in u and b’s are in pairs in v”.
Ì Exam ple 1.4.5: Give Regular expressions for the following on
Σ = { , , }
a b c
(a) all strings containing exactly one a
(b) all strings containing no more than three a’s
(c) all strings which contain at least one occurrence of each symbol in
Σ.
DFA and NFA
85