0
$\begingroup$

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 (:.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ok, but this prove that it is of another class of language, but, how to prove that it IS context free? $\endgroup$ – JB-Franco Mar 13 '18 at 22:11
  • 1
    $\begingroup$ This proves that $L$ is not context free. $\endgroup$ – posilon Mar 13 '18 at 22:12
  • $\begingroup$ I have followed your advice, and I have added something on the above. What do you think about it? $\endgroup$ – JB-Franco Mar 19 '18 at 18:53
  • $\begingroup$ 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). $\endgroup$ – posilon Mar 19 '18 at 19:50
  • 1
    $\begingroup$ 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". $\endgroup$ – posilon Mar 19 '18 at 19:51

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.