How to prove that a language is not regular without the use of the Pumping Lemma?

Question

I have an exercise to prove.

Prove that $\{a ^ i b ^ j c ^ k \mid i, j, k \geqslant 0, \text{if $i = 1$ then $j = k$}\}$ is not a regular language but that respects the conditions of the Pumping Lemma.

How can I do?

Answer 1

Hint. Take the intersection of your language with the regular language $ab^*c^*$.

Answer 2

Use closure properties: if $R$ and $S$ are regular languages, then $R\cap S$ is regular.

Let $R$ be your language $R\equiv \{a ^ i b ^ j c ^ k \mid i, j, k \geqslant 0, \text{if $i = 1$ then $j = k$}\}$.

Let $S$ be the language $S\equiv \{ab^jc^k \;|\; j,k \geqslant 0\}$. Note that $S$ is a regular language.

Assume, for contradiction, that $R$ is regular. Then $R\cap S$ must be regular. But $R\cap S$ is the language $\{ab^kc^k \;|\; k \geqslant 0\}$. You can prove using the pumping lemma for regular languages that $R\cap S$ isn't regular—which means that $R$ isn't regular either.

---

In short, although you can't use the pumping lemma directly to prove that $R $ isn't regular, you can use the pumping lemma to prove that $R\cap S$ isn't regular, which is enough to establish that $R$ isn't regular.