1
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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