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?