Theory of computation - Using the pumping lemma for context free languages
- by Tony
I'm reviewing my notes for my course on theory of computation and I'm having trouble understanding how to complete a certain proof. Here is the question:
A = {0^n 1^m 0^n | n>=1, m>=1} Prove that A is not regular.
It's pretty obvious that the pumping lemma has to be used for this. So, we have
|vy| = 1
|vxy| <= p (p being the pumping
length, = 1)
uv^ixy^iz exists in A for all i = 0
Trying to think of the correct string to choose seems a bit iffy for this. I was thinking 0^p 1^q 0^p, but I don't know if I can obscurely make a q, and since there is no bound on u, this could make things unruly..
So, how would one go about this?