Which one of the following languages is CFL and what is the grammar for it? Can we use pumping lemma for the not CFL?
\begin{align*} L_1 &= \{a^mb^ma^n \mid m,n \geq 0\}\\ L_2 &= \{a^mb^ma^n \mid m \geq n \geq 0\} \end{align*}
Asked
Active
Viewed 95 times
1 Answers
1
It’s very easy to write a context-free grammar that generates $L_1$. You might start with a production $S\to PA$ and add productions ensuring that $P$ generates $\{a^nb^n:n\ge 0\}$ and $A$ generates $a^*$.
Yes, you can use the pumping lemma for context-free languages to show that $L_2$ is not context-free; the proof is very similar to the usual example of such a proof, the proof that $\{a^nb^nc^n:n\ge 0\}$ is not context-free.
Brian M. Scott
- 616,228
-
@user1176123: You’re welcome; if you get completely stuck, feel free to ask me to expand the hints. – Brian M. Scott Apr 26 '13 at 13:14
-
@ Brian M. Scott: for $L_2$, I am assuming a string $s = a^p b^p a^p$ , where p is the pumping length. Then I am arguing that s can be composed of xuyvw. Now 2 cases: 1. u and v may only contain one symbol: not both prefix a's and b's or b's and suffix a's. Then $xu^2yv^2z$ either violates $a^m b^m$ or no of b becomes less than no of a. Is the argument correct? For case 2: is it violating the order? Thanks in advance. – Jesun Apr 27 '13 at 02:38
-
@user1176123: Yes, that’s correct: if $uyv$ contains both symbols, then $xu^2yv^2z$ contains two separate blocks of $b$’s. If $uyv$ is contained in the first $a$ block or the $b$ block, then $xu^2yv^2z$ doesn’t have the same number of $a$’s in its first block as it has $b$’s, and if it’s contained in the second $a$ block, then $xu^2yv^2z$ has too long a second $a$ block. – Brian M. Scott Apr 27 '13 at 02:47
-
@ Brian M. Scott: Thank you very much for your help – Jesun Apr 27 '13 at 03:18
-
@user1176123: You’re very welcome. – Brian M. Scott Apr 27 '13 at 03:18