I am trying to design a CFG that generates the language $\{a^k b^m a^n a^k \mid m \leq n\}$. However, I am having trouble with the $b^m a^n$ where $m \leq n$. How do I solve this?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Think of it as $b^m a^m a^k$ where $k = n-m \ge 0$ $\endgroup$– riciJun 3, 2020 at 5:24
-
$\begingroup$ So you know you'll have to generate $P\to bPa$, except sometimes the $b$ might be missing... $\endgroup$– frabalaJun 3, 2020 at 6:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You can write this language as $$ \{ a^k b^m a^m a^\ell a^k \mid k,m,\ell \in \mathbb{N} \}. $$ This description easily lends itself to conversion into a context-free grammar.
answered Jun 3, 2020 at 8:56