0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ You are confused, but so are we. Please clarify what you are asking. $\endgroup$
    – Nathaniel
    Jan 30, 2022 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$
    – Hendrik Jan
    Jan 31, 2022 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, 2022 at 16:32

0

Reset to default

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.

Browse other questions tagged or ask your own question.