Question

1. Prove by contraction that

   L = {0^x 1^y 0^x+y | x >= 1 and y >=1} is not Regular.

   Must use the Pumping Lemma.

[ HINT: Describe the language in English first. Use example 3 from the lecture notes ]

a) Choose one S from L where S is longer than N

      (Describe S in terms of N and M)

      S = **??**

b) List all places v can be in S: (i.e. all possible uvw mappings)

      (Note: v has to be in the first N chars)

      v has to be where?       ?**?

c) For each possible place for v in #2 above, is there is a way to repeat/skip v to make it

        go out of the language L?

• Where v is:                                   ?**?
• Repeat factor: i =                      ?**?
• What does u v^i w look like?    ?**?
• Is u v^i w in L?                               ?**?

   Thus, there was no way to break S into uvw and repeat or skip v

     as much as we want. We found a counter example S that does not satisfy Pumping Lemma.

d) Conclusion about L:    ?**?

Answer 1

Question : To prove that the language is not regular.

Solution : According to the pumping lemma there exists a string "s" such that it can be decomposed into three strings;

s = uvⁱ w such that

(i) v is not equal to epsilon

(ii) | xy | <= n

Upon pumping " v " , the string so obtained must be in the language L otherwise it is not regular.

The language is { 0^x 1^y 0^x+y | x >=1 and y >=1 } // Any number of zeroe's followed by any number of one's followed by the sum of occurences of previous 2 symbols

Let us take a string in L :

s = 00110000 // x =2 and y =2

Decomposing " s " into " u " , " v " and " w " .

v = 11

u = 00

w = 0000

These substrings satisfy the conditions of the pumping lemma . Moving forward :

Pumping " v " with i = 2

v = 1111

u = 00

w = 0000

s = uv²w = 0011110000 is the string obtained .

Upon observing the string it is clear that x = 2 and y =4 , so x+y = 6 .

But " w " only contain 4 zeroes rather than 6 .

Hence the string is not in the language L and it is not Regular.