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$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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$
    – Ramesh
    Jan 18, 2018 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, 2018 at 18:46
  • $\begingroup$ Is it necessary for p to be minimum pumping length? $\endgroup$
    – Ramesh
    Jan 18, 2018 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, 2018 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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