i really don't know how to get $s = xyz$ for pumping lemma for this language

180 Views Asked by At

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.

1

There are 1 best solutions below

2
On BEST ANSWER

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?