1
$\begingroup$

Let $L=\{a^i b^j c^k d^l : i, j, k, l > 0, 3(i+j) \geq 2(k+l)\}$. Proof that this language is not a regular language.

I have no clue, cause i can't find any example for $3(i+j) \geq 2(k+l)$ or something like this.

$\endgroup$
0
$\begingroup$

Alternatively, use closure properties too. We know that the regular languages are closed under reversal (if you do not know, try to proof it!).

The reversal of your language is $$ L^R = \{ d^l c^k b^j a^i \mid 2(k+l) \le 3(i+j), i,j,k,l > 0 \} $$ and for this language we can do it with the Pumping lemma. Suppose it is regular with pumping constant $N$, then consider $w = d^N c^N b^N a^N$, for which we have a decomposition $uvw = w$ with $|uv| \le N$ and $|v| > 0$, in particular $uv \in d^{\ast}$... can you complete it from here on your own?

$\endgroup$
  • $\begingroup$ no i can't. is it $d^n c^n b^{2n} a^{2n}$ and then $d^{n-i} (d^i)^m c^n b^{2n} a^{2n}$. i'm i going right? $\endgroup$ – Suparerk Yoscharoen May 6 '18 at 15:20
  • $\begingroup$ What happens to your initial segment when you pump it? Does the defining inequality still holds for words if you pump them? (surely not, here is where the contradiction comes in!) $\endgroup$ – StefanH May 6 '18 at 15:29

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.