Theory of Computing

1. Prove that

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

Must use the Pumping Lemma. [8pts]

For any N

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

(S should be described in terms of N)

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

(Note: |uv| <= N) v has to be where????

3) For each possible place for v in #2,

is there is a way to repeat/skip v to make it

go out of the language L?

o Where v is:

o Repeat factor i:

o Why uviw is not in L:

4) Conclusion about L: