2

I'm new to this website.

I want to find the grammar for the following context-free language: $$L={w|w=a^*b^ia^*b^{2i}}$$

I tried

\begin{align*} S&\rightarrow aS|\varepsilon S | bKSKb\\ K&\rightarrow\varepsilon |bK \end{align*}

I want to know if it works for any cas. It works for the following example $babb$ : \begin{align} \varepsilon S (1)\\ S(1)&\rightarrow bKSKb(2)\\ K(1)&\rightarrow \varepsilon\\ S(2)&\rightarrow aS\\ K_2(2)&\rightarrow bK(3)\\ K(3)&\rightarrow \varepsilon \end{align}

  • 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.

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 !

M.TSHIL
  • 21
  • 3

1 Answers1

0

It seems to me that your grammar is incorrect, as you'll never be able to get rid of your nonterminal start variable. Lets assume you add in another production to solve this, $S \to \varepsilon$, your language will then accept the word $bbbb$, which is not part of your language. I came up with the following productions to recognize the language,

$$ S \to aS | bSbb | A $$ $$ A \to \varepsilon | aA $$

awright96
  • 425