I need to show that the following language is not regular.

$$L = \{\ ab^jc^j\ |\ j \geq 0\ \}\ \cup\ \{\ a^ib^jc^k\ |\ i, j, k \geq 0 \ and\ i \neq 1\ \}$$

There is also a hint that it cannot be proven just with using the Pumping Lemma. Closure properties must also be used.

I'm having a hard time with this one. Any help would be appreciated.


2 Answers 2


Let $ L_1 = \{\ ab^jc^j\ |\ j \geq 0\ \} $ and $ L_2 = \{\ a^ib^jc^k\ |\ i, j, k \geq 0 \ and\ i \neq 1\ \} $. Then

$$ L = L_1 \cup L_2. $$

If we take $$ \begin{align} L\ \cap\ ab^*c^* &= (L_1\cup L_2) \cap ab^*c^* \\ &= (L_1\cap ab^*c^*)\ \cup\ (L_2 \cap ab^*c^*)\\ \end{align} $$

Since $L_1\cap ab^*c^* = L_1$ and $L_2 \cap ab^*c^* = \emptyset$, we have

$$ L\ \cap ab^*c^* = L_1 $$

Now, $ab^*c^*$ is regular, and $L_1$ is not regular (can be shown using the Pumping Lemma). If $L$ was regular, by the closure properties, $L_1$ would be to, which is a contradiction. Hence, $L$ is not regular.


Here is a further hint. $L$ consists of two parts. One of them as a language by itself is not regular. Can you see which part?

Can you carve out that part as the intersection of $L$ with another regular language?

  • $\begingroup$ I posted a solution. Got it right??? $\endgroup$
    – Da Mike
    Apr 23, 2019 at 16:51
  • $\begingroup$ Yes. $ \quad $. $\endgroup$
    – John L.
    Apr 23, 2019 at 17:07

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.