1
$\begingroup$

$L$ = $0^p1^q0^p$. Where $p, q \geq 0$

Here for any string $w \in L$ , I can have $u$=$0^p$, $x$ = $1^q$ and $v$= $0^p$ and $x^i$ will belong to L for all $i \geq 0$

So how do I prove it to be non regular using pumping lemma as there doesn't exist a string $w \in L$ which cannot be decomposed into the form $ux^iv$ for all $i \geq 0$.

$\endgroup$
1
$\begingroup$

Don't forget that the pumping lemma guarantees that $|ux| \leq n$, where $n$ is the pumping length (which is also a lower bound on the length of $w$). You can use this condition to forbid the situation you describe.

$\endgroup$
  • $\begingroup$ Suppose I have w = 00011000. Here |w| = 7. We can have u = 000, x=1, v=1000 which satisfies pumping lemma. I didn't quite understand your answer. Is n=1 (or pumping length =1) here as we can have $1^q$ alone which belongs to the language.? $\endgroup$ – Rajesh R Jan 18 '18 at 18:39
  • $\begingroup$ I suggest reviewing the Wikipedia article on the pumping lemma for regular languages (which uses $p$ for the pumping length). $\endgroup$ – Yuval Filmus Jan 18 '18 at 18:46
  • $\begingroup$ Is it necessary for p to be minimum pumping length? $\endgroup$ – Rajesh R Jan 18 '18 at 19:03
  • $\begingroup$ It's best for you to try to solve the exercise using my hint, without any further help. $\endgroup$ – Yuval Filmus Jan 18 '18 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.