35. Assume L
n n
= {
}
0 1
2
is regular. Assume S is the set of states of a finitestate machine recognizing the set. Let Z
n n
= 0 1
2
where 3n s
≥ | |. Then by
pumping lemma, Z
uvw l v
n n
=
=
≥
0 1
1
2
, ( ) , and uv w
n
i
n n
∈
≥
{
|
}.
0 1
0
2
It
is obvious that V cannot contain both 0 and 1, since V
2 could then
contain 10. Therefore V is all 0s or all 1s, and so uv
2 w contains too many
0s or too many 1s, so it is not in L. This is a contradiction which shows L
is not regular.
36. Assume that the set of palindromes over {0, 1} is regular. Assume S is
the set of states of a finite-state machine that recognizes the set. Let Z =
0
n 10
n , when n > | S |.
Apply the pumping lemma to get uv w L
i
∈ for all positive integers i
where l v
( ) ≥1, and l uv s
( ) | |
≤ and z
uvw
n
n
=
=
0 10
. Then v must be a
string of 0s (since | | | | )
n s
> , so uv
2
w is not a palindrome. Therefore the set
is not regular.
37.
38. (ab ∪ a)*
314
Theory of Automata, Formal Languages and Computation
φ
{3}
{1}
{1,3}
{2}
{2,3}
{1,2}
{1,2,3}
a,b
a
b
b
a
b
a
b
a
a
b
a,b
ε
ε
ε
ε
ε
ε