2
$\begingroup$

I am currently solving a problem in which we have to show that we can not prove using pumping lemma that the language mentioned in the question is not regular.Here is the full question

Consider the language F = {$a^i b^j c^k$ | i, j, k ≥ 0 and if i = 1 then j = k}.

a. Show that F is not regular.

b. Show that F acts like a regular language in the pumping lemma. In other words, give a pumping length p and demonstrate that F satisfies the three conditions of the pumping lemma for this value of p.

c. Explain why parts (a) and (b) do not contradict the pumping lemma.

But, I am able to prove it using pumping lemma that language is not regular. For that I take:

pumping length as 3

x:a ; y:b ; z:c

$xy^lz$ ∈ F for l = 1

$xy^lz$ ∉ F for l > 1

Is there some problem with the above shown proof or the question is wrong.

$\endgroup$

1 Answer 1

3
$\begingroup$

For that I take:

x:a ; y:b ; z:c

You can't do that. You have to first give a pumping length $p$ and then you have to show that there is no decomposition of the word $abc$ into $xyz$ with $|y|\ge 1$ and $|xy| \le p$ for which $xy^n z \in F$. If we take your word $abc$ and decompose as $x=\varepsilon$, $y = a$, $z=bc$ then the pumped words are $a^nbc$ and are all in $F$.

$\endgroup$
4
  • $\begingroup$ I forgot to mention that I have taken pumping length as 3. Now, I have added it to the question. So, in this case is the proof correct. $\endgroup$
    – V K
    Sep 19, 2018 at 3:20
  • $\begingroup$ You haven't understood my point: the proof strategy is completely flawed because showing the existence of a decomposition which can't be pumped is not the same as showing the non-existence of a decomposition which can be pumped. $\endgroup$ Sep 19, 2018 at 6:09
  • $\begingroup$ So, if ,even a single decomposition exists for which pumping lemma holds true then language is said to be regular? $\endgroup$
    – V K
    Sep 19, 2018 at 6:35
  • $\begingroup$ The answer to that question is implicit in part (c) of your original problem. $\endgroup$ Sep 19, 2018 at 21:00

Your Answer

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

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