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

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$$?

• Doesn't the use of "or" in the language description to join three possible conditions give you a clue? – rici Nov 19 '18 at 18:24

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.