2.8 Pumping Lemmas 87
(1) Both i and j are greater than or equal to n. Then, (x: = an and x = cn
and so ancn E L’.
(2) The integer i is less than n. Then, x = udbcnviD1 and x = cn and so
(.&2n-i-l E L’. Note that i + (2n - i - 1) = 2n - 1 is odd.(3) The integer j is less than n. Similar to case (2) we get a2”+jw1bcj E L’.
Thus, we can see that
L’ = {uncn 1 n > 0) U {umbcn 1 r-n+ n is odd}.
It follows that L’ is not regular, since L’ n uc = { uncn 1 n > 0) is not regular
(by Example 2.60). cl
Exercise 2.8
- Show that the following languages are not reguhr.
(a) {On3+3n2-2n 1 n 2 0).
(b) (OPIQOmln 1 p + q = m + n,p, q, m, n > 0).
(c) {Omln Im,n>Oandm#2n+l}. -
(d) {Omln I2n < Yr2 < 3n,m,n > 0).
(4 +J E {o,1,2 I #o(w) + #&, = #2(w)}
(f) {O”Q I p and 4 are primes}. - For each of the following languages, determine whether it is regular.
Present a proof for your answer.
(a) The set of binary strings having an equal number of O’s and 1’s.
(b) The set of binary strings having an equal number of 01’s and 10’s.
(c) The set of binary strings having an equal number of 010’s and
101’s.
0 bY I IxfJ Y E -to, 1), 14 = IYL #o(z) 2 #o(Y))
(4 bYX I xf, Y, x E (0, o, I4 = I4 > 0, #o(x) 2 #o(z)}
(f) b#Y#Z I X:YY, x are binary expansions of positive integers satis-
fying x + y = x}.
- Let I be the alphabet of Example 2.65.
(a) Show that the set L of all strings over alphabet I’ that represent
correct division is not regular. For example,
1 1 1 1
-r. 0 1 0 1
0 0 1 1
implies that the following string is in L:
- Let I be the alphabet of Example 2.65.
(s)(a)(i)(i)*