Let $\Sigma = \{a, b, c\}$ and $L = \{wa^{1 + k + 2n}b^nw^{rev}\mid n, k \in \mathbb{N}_0, w \in \Sigma^*\}$. It is clear that $L$ is context free, but the question is the following:

Let $L'$ be the language of all words $z \in L$, where between the $i$-th and the $(i+1)$-th occurence of the substring $abc$, $z$ has at least $2i$ occurences of $b$. Then prove that $L'$ is not context-free.

My first intuitions were to go about it using the pumping lemma for CFL, but things started to get nasty quite quickly, because firstly I couldn't find the perfect word to contradict it and secondly, the considerable cases for the positioning of the pumpable substring are way too many provided even the bare minimal conditions for the quasi "perfect word". So I ended up giving up on that idea and instead searching for alternatives, but unfortunately my arsenal is not that broad - I tried exploiting closure properties of CFL (mostly closedness under intersection with regular languages), but couldn't figure it out either. So I'd be really interested if there are any slick alternatives that could provide a reasonable proof! Many thanks in advance!


1 Answer 1


Define $$ L_0 = L' \cap (b^+abc)^*(cba b^+)^* = \\ \{ ww^{\mathit{rev}} \mid w \in (b^+abc)^*, ww^R \in L' \}. $$ Now let $h$ be a homomorphism mapping $a,b,c$ to themselves and $d,e,f$ to $a,b,c$, and let $k$ be the homomorphism that maps $a,b,c$ to themselves and deletes $d,e,f$. Then $$ L_1 = k(h^{-1}(L_0) \cap (b^+abc)^*(fede^+)^*) = \\ \{w \in (b^+abc)^*, ww^R \in L'\}. $$ Now let $r(a) = abc$ and $r(b) = bb$, and consider $$ L_2 = r^{-1}(L_1) = \{ b^{n_1} a b^{n_2} a \dots b^{n_m} a : n_i \geq i \}. $$ We now apply the pumping lemma on the word $bab^2ab^3a \ldots b^p a$ for large enough $p$. The pumping lemma decomposes this word as $uvwxy$, where $vy \neq \epsilon$ and $v,y$ can be pumped. suppose that $v \neq \epsilon$. If $v \in b^+$ then $uv^0wx^0y \notin L_2$. If $v$ contains an $a$ then $uv^2wx^2y \notin L_2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.