I want to find the grammar for the following context-free language:
$L=\{w|w=a^ib^ja^jb^{i}\}$
I tried
\begin{align*} S&\rightarrow \varepsilon|aKb |aSb\\ K&\rightarrow\varepsilon |bKa \end{align*}
I want to know if it works for any cas. It works for the following example $aababb$ :
\begin{align} aSb (1)\\ S(1)&\rightarrow aKb(2)\\ K(2)&\rightarrow bKa(3)\\ K(3)&\rightarrow \varepsilon\\ \end{align}
Something is missing: the grammar rule we use. If you have also a better way to explain the outpu, I would be glad to hear it from you !
- In parenthesis it is the step in which we are on the right of the arrow and which we use on the left.
- In indice it is the position of the character we change.
If you allow $i=0$, then the grammar you give does not generate $b^ja^j$. Try the one below: $$S\rightarrow \varepsilon\;|\;aKb\;|\;bHa$$ $$K\rightarrow \varepsilon\;|\;aKb\;|\;bHa$$ $$H\rightarrow \varepsilon\;|\;bHa$$