164 9 Theory of Computer Science
EXAMPLE 5.19
Show that L = {ai' 1 p is a prime} is not regular.
Solution
Step 1 \Ve suppose L is regular. Let II be the number of states in the finite
automaton accepting L.
Step 2 Let p be a prime number greater than n. Let }t' = a F . By pumping
lemma. H' can be written as w =xyz. with 1 xy 1 ~ nand !y 1 > O. x, y. z are
simply strings of a's. So. y = a
lll for some 111 e: 1 (and ~ n).
Step 3 Let i =p + 1. Then ! .r";z I = I·\\'z I + 1)' 1-11 =p + (i - l)m =p +
pm. By pumping lemma. . \).iz E L. But 1 xylZ I = p + pm =p(l + 111). and p(l
+ m) is not a prime. SO A}J Z EO L. This is a contradiction. Thus L is not regular.
EXAMPLE 5.20
Show that L = {O
i l 1 lie: I} is not regular.
Solution
Step 1 Suppose L is regular. Let n be the number of states in the finite
automaton accepting L.
Step 2 Let w = O"l/l. Then l}t,! = 271 > n. By pumping lemma, we write
W =:I.I' Z with IX}'I ~ n and I y I ::t O.
Step 3 We want to find i so that x.'/z EO L for getting a contradiction. The
string \' can be in any of the following fonns:
Case 1 y has a's. i.e. y = Ok for some k e: l.
Case 2 ,'has only l' s. i.e. y = 11 for some I 2: 1.
Case 3 y has both O· sand l' s, i.e. y = Okl
j for some k, j e: L
In Case 1. we can take i =O. As .'}.:: = 0"1". xz = on-kI". As k 2: 1. n -
k ::t n. So, xz EO L.
In Case 2. take i = O. As before, xz is 0"1',-1 and n ::t n - I. So. xz liE L.
In Case 3. take i =2. As xvz =OH- k Okljl"-: i . AI/Z: =O"-k Okl j O k l j l"-:f. As xv
2 z
is not of the fonn Oil', ,\}'2 Z EL . '
.
Thus in all the cases we get a contradiction. Therefore. L is not regular.
EXAMPLE 5.21
Show that L = {WH' I W E {(I, b} *} is not regular.
Solution
Step 1 Suppose L is regular. Let n be the number of states in the automaton
1\1 accepting L.
EXAMPLE 5.19
Show that L = {ai' 1 p is a prime} is not regular.
Solution
Step 1 \Ve suppose L is regular. Let II be the number of states in the finite
automaton accepting L.
Step 2 Let p be a prime number greater than n. Let }t' = a F . By pumping
lemma. H' can be written as w =xyz. with 1 xy 1 ~ nand !y 1 > O. x, y. z are
simply strings of a's. So. y = a
lll for some 111 e: 1 (and ~ n).
Step 3 Let i =p + 1. Then ! .r";z I = I·\\'z I + 1)' 1-11 =p + (i - l)m =p +
pm. By pumping lemma. . \).iz E L. But 1 xylZ I = p + pm =p(l + 111). and p(l
+ m) is not a prime. SO A}J Z EO L. This is a contradiction. Thus L is not regular.
EXAMPLE 5.20
Show that L = {O
i l 1 lie: I} is not regular.
Solution
Step 1 Suppose L is regular. Let n be the number of states in the finite
automaton accepting L.
Step 2 Let w = O"l/l. Then l}t,! = 271 > n. By pumping lemma, we write
W =:I.I' Z with IX}'I ~ n and I y I ::t O.
Step 3 We want to find i so that x.'/z EO L for getting a contradiction. The
string \' can be in any of the following fonns:
Case 1 y has a's. i.e. y = Ok for some k e: l.
Case 2 ,'has only l' s. i.e. y = 11 for some I 2: 1.
Case 3 y has both O· sand l' s, i.e. y = Okl
j for some k, j e: L
In Case 1. we can take i =O. As .'}.:: = 0"1". xz = on-kI". As k 2: 1. n -
k ::t n. So, xz EO L.
In Case 2. take i = O. As before, xz is 0"1',-1 and n ::t n - I. So. xz liE L.
In Case 3. take i =2. As xvz =OH- k Okljl"-: i . AI/Z: =O"-k Okl j O k l j l"-:f. As xv
2 z
is not of the fonn Oil', ,\}'2 Z EL . '
.
Thus in all the cases we get a contradiction. Therefore. L is not regular.
EXAMPLE 5.21
Show that L = {WH' I W E {(I, b} *} is not regular.
Solution
Step 1 Suppose L is regular. Let n be the number of states in the automaton
1\1 accepting L.