I have just started my masters without any substantial experience in programming and I am struggling to understand certain concepts. I have been given the following language $$L = \{a^i b^j c^k \mid i, j, k ≥ 0, \text{ if } i = 1 \text{ then } j = k\}.$$

However, I am struggling to find a way to prove that it is not regular using $L′ = \{ab^i c^i \mid i ≥ 0\}$. Also, what am I meant to do when I am given a pumping length of 2, and I have to prove that L satisfies the requirements of the regular language pumping lemma for strings longer than 2. I think I am a bit confused.

  • $\begingroup$ You are confused, but so are we. Please clarify what you are asking. $\endgroup$
    – Nathaniel
    Jan 30 at 17:27
  • $\begingroup$ This is a typical example of a language that is not regular, yet satisfies the pumping lemma for regular languages. A very similar example is given here: Languages that satisfy the pumping lemma but aren't regular?. Same techniques. For nonregularity use closure under intersection of the regular languages. On the other hand we can always pump the first symbol of the string. $\endgroup$ Jan 31 at 9:28
  • $\begingroup$ Here is how you can prove $L$ is not regular. Prove that $L'$ is not regular. Verify that the intersection of $L$ and $ab^*c^*$ is $L'$. Note that $ab^*c^*$ is regular. Then use the fact that "the regular languages are closed under the intersection operation." $\endgroup$
    – John L.
    Feb 16 at 16:32


Your Answer

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

Browse other questions tagged or ask your own question.