Theory of Computing. Using the pumping lemma for contextual free languages.

Question

I am reviewing my notes for my course in Computational Theory, and I am having trouble understanding how to complete a particular proof. Here is the question:

A = {0^n 1^m 0^n | n>=1, m>=1} Prove that A is not regular. 

It is quite obvious that for this we need to use the pumping lemma. So we have

• | yy | > = 1
• | Ear | <= p (p is the pump length,> = 1)
• uv ^ ixy ^ iz exists in for all i> = 0

Trying to think of the right row for selection seems a bit inconvenient for this. I thought 0 ^ p 1 ^ q 0 ^ p, but I don’t know if I can vaguely make q, and since there are no restrictions on u on u, this can make things unshakable.

So how would this be done?

Answer 1

It will be much easier if you use the definition of the pumping lemma applied to common languages, and not to CFG applications. Three conditions that any regular string s = xyz must have:

• For each i> = 0 xy ^ iz is in A
• | at | > = 0
• | x | <= p

Try again using 0 ^ p1 ^ q0 ^ p using these three conditions.

Hint: since we have 0 ^ p, y will consist only of 0. Therefore, when we “pump” more than y (consider xyyz), we will not get a string in the language.

Answer 2

You are using the wrong pumping lemma ... A has no context here, but it is not regular.

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

This should show you the lemma you need ... If you start with this, you can come up with an answer. If not, let me know and I will edit my answer to give you some tips.

Answer 3

I would solve this without the lemma: - Consider h (a), where h (1) = 1 h (2) = 0 h (0) = 0. Applying h ^ -1 in your language, and then the intersection with 0 ^ * 1 ^ 2 ^ give you the language 0 ^ n1 ^ m2 ^ n. - Now we use h '(a), where h' (0) = a, h '(1) = epsilon, h' (2) = b. You get ^ nb ^ n which is not regular.

Why is it easier? Because after learning these basic tricks, you can easily solve these problems.

As for the lemma: - You will need that any substring of the word in when used as a substring destroys your language. There are 6 cases that I can see (only 0 from the beginning, 0 from the beginning from 1, etc.)

As already added, you do not need a CF lemma. The CF lemma is used to show that a language is usually not CF.