0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I posted a solution. Got it right??? $\endgroup$ – Da Mike Apr 23 at 16:51
  • $\begingroup$ Yes. $ \quad $. $\endgroup$ – Apass.Jack Apr 23 at 17:07
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

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