Context-free language or not

109 Views Asked by At

It is language: $L = \left\lbrace a^ib^jc^kd^l \mid i+k < j+l+3 \right\rbrace$ Is it context-free or not?

I have two versions:

1)Pumping lemma(refute): get a word $uvxyz = aabcd$ if $i=2$ we get 2 < 3 - the word in the language pump up i, from $i=4$ the word not in the language

2)To reduce the problem to a known: We know, what $L = \left\lbrace a^nb^nc^n \right\rbrace$ is not context free , with $i=j=l=n, k=0$ the inequality $n+0 < n+n+3$ , the word in the language. Therefore, language is not context free

1

There are 1 best solutions below

0
On

Neither of your arguments works.

  • When you use the pumping lemma, you are not allowed to specify $u,v,x,y$, and $z$: all you know is that if $s$ is a word in the language that is at least as long as the pumping length $p$, then $s$ has some decomposition $s=uvxyz$ such that $|vxy|\le p$, $|vy|\ge 1$, and $uv^kxy^kz$ is in the language for each $k\ge 0$.

  • The fact that the language has a subset that is not context-free does not imply that the language itself is not context free. After all, $\{a,b,c\}^*$ contains the language $\{a^nb^nc^n:n\ge 0\}$, and $\{a,b,c\}^*$ is not just context-free, but even regular.

In fact the language is context-free; I’ll sketch the construction of a pushdown automaton that recognizes it.

Assume that the input has the form $a^ib^jc^kd^\ell$; you can use the states to ensure that any word not of this form is rejected.

Push an $A$ onto the stack for each $a$. Pop one for each $b$ until the stack empties, at which point push a $B$ onto the stack for each $b$ of input. After $a^ib^j$ has been read, the stack is empty if $i=j$, contains $A^{i-j}$ if $i>j$, and contains $B^{j-i}$ if $j>i$.

If $i\ge j$, meaning that the stack is empty or has an $A$ on top, push an $A$ onto the stack for each $c$, so that after $c^k$ has been read, the stack contains $A^{i-j+k}$.

If $i<j$, meaning that the stack has a $B$ on top, pop a $B$ for each $c$ until the stack is empty, then push an $A$ for each $c$. After $c^k$ has been read, the stack is empty if $k=j-i$, contains $B^{j-i-k}$ if $k<j-i$, and contains $A^{k-j+i}$ if $k>j-i$.

At this point the stack contains $A^{i-j+k}$ if $i-j+k\ge 0$ and $B^{-(i-j+k)}$ if $i-j+k<0$.

If the stack is empty or has an $A$ on top, pop an $A$ for each $d$ until either the end of the input is reached, or the stack empties. If the stack empties, push a $B$ onto the stack for each remaining $d$.

If the stack has a $B$ on top, push a $B$ onto it for each $d$.

  • If the stack is now empty, $i-j+k-\ell=0$.

  • If the stack has an $A$ on top, then $i-j+k-\ell>0$, and the stack is $A^{i-j+k-\ell}$.

  • If the stack has a $B$ on top, then $i-j+k-\ell<0$, and the stack is $B^{-(i-j+k-\ell)}$.

The word should be accepted if and only if $i-j+k-\ell\le 2$. This is clearly true if the stack is empty or has a $B$ on top. If the stack has an $A$ on top, it’s true if and only if the stack contains at most $2$ $A$s; you can check this with $\epsilon$-transitions to states used only for this purpose.