! Exercise 4.1.2: Prove that the following are not regular languages. a) (0\" I

Question

! Exercise 4.1.2: Prove that the following are not regular languages. a) (0" I n is a perfect square). b)(or 1 n is a perfect cube). c) (0t I n is a power of 2). d) The set of strings of O's and 1's whose length is a perfect square. e) The set of strings of 0's and 1's that are of the form ww, that is, some string repeated. f) The set of strings of 0's and 1's that are of the form wwR, that is, some string followed by its reverse. (See Section 4.2.2 for a formal definition of the reversal of a string.) g) The set of strings of O's and 1's of the form wi, where is formed from w by replacing all 0's by 1's, and vice-versa; e.g., 011 100, and 011100 is an example of a string in the language. h) The set of strings of the form wl", where w is a string of 0's and I's of length n.

Explanation / Answer

1.L = {0^n | n is a perfect square}

Prove that it is non Regular

Using pumping lemma:

L is infinite. suppose L is also regular.

according to pumping lemma there exists an integer n such that for every string w.

w = xyz where |w| >=n

|y|> 0, |xy| <=n and for all k >=0, the string xykz is also in L.

choose w to be w =0p where p= n2 that is it is a perfect square.

let w =0000...000 = xyz. (w = p = n2)

let |xy| <= n and |y| = k

i.e., w= 0000 0k 000...

X = 000, Y =0k z= 000

So, |xyz| = |xz| + 2|y| = (n2 - k) + (k)

|xy2z| = |xz| + |y| = (n2- k) + 2k = n2 + k

where n2 + k < n2 + n (k<=n as |xy| <= n and |y| = k)

<n2 + 2n + 1

(n+1)(n+1) and

n2 + k > n2 (k>0)

n2 <  n2 + k < (n+1)2

2. L = {0^n | n is a perfect Cube}

Prove that it is non Regular

Using pumping lemma:

L is infinite. suppose L is also regular.

according to pumping lemma there exists an integer n such that for every string w.

w = xyz where |w| >=n

|y|> 0, |xy| <=n and for all k >=0, the string xykz is also in L.

choose w to be w =0p where p= n3 that is it is a perfect cube.

let w =0000...000 = xyz. (w = p = n3)

let |xy| <= n and |y| = k

i.e., w= 0000 0k 000...

X = 000, Y =0k z= 000

So, |xyz| = |xz| + |y| = (n3 - k) + (k)

|xy2z| = |xz| + 2|y| = (n3- k) + 2k = n3 + k

where n3 + k < n3 + n (k<=n as |xy| <= n and |y| = k)

<n3 + 3n2 + 3n + 1

(n+1)3 and

n3 + k > n3 (k>0)

n3 <  n3 + k < (n+1)3

3. 0^n n is a power set of 2

power set of 2 : a,aa,aaaa,aaaaaaaa, etc.,

we have as = xyz where s= 2n ,

|y| >0, |xy|<= p, xyiz belomngs L such that i>=0

next step: xy2z cannot be a element of L

4. L is the set of dtrings of 0's and 1's whose length is a perfect square

Prove that it is non Regular

Using pumping lemma:

L is infinite. suppose L is also regular.

according to pumping lemma there exists an integer n such that for every string w.

w = xyz where |w| >=n

|y|> 0, |xy| <=n and for all k >=0, the string xykz is also in L for all p>=0.

then supose that N is the smallest perfect square greater than or equal to n,

let w belongs L so that |w| = N

w= xyz with |xy| =<= n, |y| >0 and xyp belongs L for all p>0 (using pumping lemma)

So, xy2z belongs L but |xy2z| cannot be a perfect square

the next perfect square is n2 = 2n + 1 and xy2z cannot have length morethan N + n, which is not a perfect square.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.