1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ it involves the language a^nb^n which is not regular and FM can't count unlimited number. $\endgroup$ – Mr. Sigma. Dec 3 '18 at 8:43
1
$\begingroup$

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

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

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.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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.

|cite|improve this answer
$\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.