Is $L = \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ context free language?

Question

I have doubt , regarding this question

Is this language is context free ?

$L= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$

---

IMO : push all $a$'s , match with $a$ and pop $b$'s ,(now stack is empty , if the string leading to given language), escape $c$ , escape all $a$'s , now I can't match last $b$'s with either $a^m$ or $b^m$ .

Can you do it with single stack ?

Answer 1

This language is a variation on the language $L_3 = \{a^mb^mc^m \mid m \in \mathbb{N}\}$. $L_3$ is not context-free (CF), and the tool used to prove that is the pumping lemma for CF languages.

Suppose $L = \{a^mb^mca^nb^m \mid m, n \in \mathbb{N}\}$ is CF. The pumping lemma for CFLs applies:

There is an $N \in \mathbb{N}$ such that for every $s \in L$ of length $|s| \ge N$,

• $s$ can be written as $s = xuyvz$,
• $u \neq \varepsilon$ or $v \neq \varepsilon$ (or both),
• $|uyv| \le N$, and
• $xu^iyv^iz \in L$ for all $i \ge 0$.

We make use of this by choosing $s \in L$ long enough that that "pumping" (repeating) $u$ and $v$ gives a string that no longer can be in $L$. Let $$ s = a^{N+1}b^{N+1}cb^{N+1} $$ Then however you decompose this $s$ into $s = xuyvz$ with $|uyv| \le N$, $u$ (if $u \neq \varepsilon$) or $v$ (if $v \neq \varepsilon$) will have to occur in the string at places such that $$ s_2 = xu^2yv^2z $$ no longer fits the definition of $L$.

You have to consider all the possible extents in the string:

Suppose $u$ is nonempty. If $u$ falls within the first string of $a$s, $a^{N+1}$, then $uyv$ has to end before the 'c', so $s_2$ has more $a$s and $b$s before the $c$ than $N+1$, but the number of $b$s at the end will still be $N+1$; so $s_2 \notin L$. If $u$ straddles the initial $a$s and $b$s then $s_2$ will contain $a$s after its first run of $b$s before the $c$, so again $s_2 \notin L$. If $u$ begins at the $c$ then doubling it repeats $c$, so $s_2 \notin L$. Finally, if $u$ falls within the last run of $b$s then the final run of $b$s in $s_2$ is longer than the initial runs of $a$s and $b$s, so again $s_2 \notin L$.

Similarly if $u$ is empty but $v$ isn't.

So $L$ is not context-free.