0

Having the following language:

$$L = \{ a^jb^mc^m : 0 \le j \le m \}$$ I have to prove that it is context free.

I have tried to consider the concatenation of smaller context free languages, to take advantage of the fact that the concatenation of context free languages, still results in a context free language, but, I can't, because the quantity of $a$ is dependent from $b,c$, I can't separate that languages.

So, another way, I have tried to construct a context free grammar, but, without success, because, I have obtained that the $a$ can be produced without restrictions:

$$ \begin{array}{lcl} G & = & (X,V,S,P) \\ X & = & \{ a,b,c \} \\ P & = & \left \{ \begin{array}{lcl} S & \rightarrow & \underset{(1)}{\lambda} & \Biggm | & \underset{(2)}{aA} \\ A & \rightarrow & \underset{(3)}{aA} & \Biggm | & \underset{(4)}{B} \\ B & \rightarrow & \underset{(5)}{bBc} & \Biggm | & \underset{(6)}{\lambda} \\ \end{array} \right \} \end{array}$$ Please, can you help me? How can I contruct a proper grammar for that language?

Thanks! (:

In ADDITION:

to find a proper CF grammar, proves only that the language is at least CF, so, it is not the proper way to proceed.

I have followed the advice of the user @posilon.

I post only a particular case, where I don't encounter any contraddiction, because writing the entire exercise it is too long. In the result I obtained, I can declare that the language IS context free.

In the case when $v$ contains all of $a$ and $x$ contains all of $b$, where :

$$vwx = a^kb^l, \quad 2 \le k+l \le p$$

$$\begin{array}{lcl} v & = & a^{k_1}b^{l_1}\\ x & = & a^{k_2}b^{l_2} \end{array}$$

considering the pumped string :

$$uv^2wx^2y = a^{p+k_1+k_2}b^{p + l_1 + l_2}c^p$$

I obtain:

$$\begin{array}{lcl} uv^2wx^2y & = & a^{p+k_1+k_2}b^{p + l_1 + l_2}c^p \\ & = & a^{p+k+0}b^{p + 0 + l}c^p \\ & = & a^{p+k}b^{p+l}c^p \end{array}$$

check if the initial condition is still valid:

$$\begin{array}{lcl} 0 & \le & p+k & \le & p+l \\ - p & \le & k & \le & l \end{array}$$

it's TRUE, $k \ge 1, l \ge 1$. So $L$ is CF. What do you think? Thanks again (:.

JB-Franco
  • 852

1 Answers1

1

You can use Ogden's lemma to show that $L$ is not context free.

Proof sketch:

Using the notation of the Wikipedia article, let $s=a^pb^pc^p \in L$ and mark every $a$. Suppose that $L$ is context free. By Ogden's lemma, we can write $s=uvwxy$ so that $vx$ has contains at least one marked symbol and $uv^nwx^ny\in L$ for all $n \geq 0$. The latter implies that $v=b^i$ and $x=c^i$ for some $i$, since the length of $vx$ is at least $1$. This is a contradiction since then $vx$ fails to have any marked positions.

posilon
  • 2,253
  • Ok, but this prove that it is of another class of language, but, how to prove that it IS context free? – JB-Franco Mar 13 '18 at 22:11
  • 1
    This proves that $L$ is not context free. – posilon Mar 13 '18 at 22:12
  • I have followed your advice, and I have added something on the above. What do you think about it? – JB-Franco Mar 19 '18 at 18:53
  • Your addition makes no sense to me for a number of reasons. First of all, a given language either is CF or not. Finding a CF grammar that generates that language is a perfect way to prove that that language is CF. Alternatively, another way to prove that a given language is CF is to show that it is recognized by a (nondeterministic) pushdown automaton. Secondly, if you say "suppose the statement $X$ holds" and you don't reach a contradiction then you haven't proved that $X$ holds. The only thing that you may be prove after this point is that $X$ is false (by reaching a contradiction). – posilon Mar 19 '18 at 19:50
  • 1
    In particular, Ogden's lemma and the pumping lemma are not useful in proving that a language is CF, but they may be used to show that a language is not CF. Thirdly, $(ab)^2=abab\neq a^2b^2$ and more generally $(a^kb^l)^2=a^kb^la^kb^l$. Fourthly, if $l \geq 1$ then $a^{p+k}b^{p+l}c^p \notin L$ because $p+l \neq p$. Finally, unless there is a mistake in the proof I provided, you won't be able to show that $L$ is CF, no matter how hard you try, because there is a proof that $L$ is not CF. That's the whole concept of "proof". – posilon Mar 19 '18 at 19:51