# Show language not regular

How can I show that $$\{a^ib^jc^k|i=0 \lor j=k\}$$ is not regular?

I tried applying the pumping lemma but it does seem to have a pumping length of 1?

Alternatively there is the Myhill–Nerode theorem. Are $$\{a^ib^j|i=0 \lor j\in\mathbb{N}\}$$ infinite many equivalence classes?

• it involves the language a^nb^n which is not regular and FM can't count unlimited number. – Mr. Sigma. Dec 3 '18 at 8:43

## 3 Answers

Consider the intersection of your language with $$ab^*c^*$$.

• Then we would get the nonregular language $b^nc^n$ but which theorem can I use on the intersection? – Mark Regev Nov 17 '18 at 11:51
• Closure under intersection. – Yuval Filmus Nov 17 '18 at 15:17

Myhill-Nerode theorem: For every j, j' the strings $$ab^j$$ and $$ab^{j'}$$, $$j ≠ j'$$, can be distinguished - because one can be followed by $$c^j$$ and the other can't.

You could try with Pumping Theory (P.T.) of Regular Languages, that is to assume the language is regular and pick $${n}$$ in P.T. as $${n=j=k}$$. Then follow the three rules in P.T. for a contradiction.