1

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.
Revolucion for Monica
  • 1,511
  • So you'd use the first rule $i$ times and second rule $j$ times? BTW, I'm not sure what your questions are. I understand the question about if it works for any cas, but not the part after the production rules. – Χpẘ Apr 25 '17 at 00:20
  • Do you allow $i$ and $j$ to be zero? – Prajwal Kansakar Apr 25 '17 at 01:54

1 Answers1

0

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

Prajwal Kansakar
  • 5,391