Show that the following language is context-free/not context free by expressing the language as the union of three other languages.

134 Views Asked by At

I want to show that the language $L = $ {$a^mba^nba^p:m=n $ or $n = p$ or $m = p$} is either context-free or not context free by expressing the language as a union of three other languages $L_1$, $L_2$, and $L_3$.

By knowing if these three other languages are context-free/not context-free, I hope to indicate whether the language $L$ is context-free/not context-free.

Can anyone help me pick these three other languages that when unioned together form $L$?

1

There are 1 best solutions below

0
On

Let $L_1=\{a^mba^nba^p:m=n\}$. Consider the following grammar that generates this language with starting symbol $S$: $$ S\longrightarrow Cb\text{ }|\text{ }Sa \\ C \longrightarrow b\text{ }|\text{ }aCa $$ This grammar is context-free, so $L_1$ is context-free. A similar grammar will show that $L_2=\{a^mba^nba^p:n=p\}$ is context-free.

Let $L_3=\{a^mba^nba^p:m=p\}$. Consider the following grammar that generates this language with starting symbol $S$: $$ S\longrightarrow bCb\text{ }|\text{ }aSa \\ C \longrightarrow \epsilon\text{ }|\text{ }aC $$ This grammar is context-free, so $L_3$ is context-free. Since $L=L_1\cup L_2\cup L_3$, then $L$ is context-free.