Find an s-grammar for L={a^nb^2n : n>=2}

Question

i can't find s-grammar(Simple grammar) for this language and s-grammar has the restricted form like

A -> ax

where A∈V, a∈T, x∈V*, and any pair (A, a) occurs at most once in production P.

how can i find the s-grammar for this language?

i found that the corresponding CFG for this language is:

S -> aaAbbbb,
A -> aAbb | ϵ

Answer 1

First, there is the problem of the empty word. For that, just consider:

• $S\to aaAbbbb\mid aabbbb$
• $A \to aAbb \mid abb$

There is still the problem of multiple rules from the same variable beginning by the same terminal. For that, you'd need to be able to stop the derivation. For that, replace the rules by:

• $S\to aaAbbb$
• $A \to aAbb \mid b$

Then, may seem artificial, but you could just replace each apparition of a terminal in a rule not in the first position by a variable, and add a rule to replace this variable by the corresponding terminal.

For example, replace $S\to aaAbbb$ by $S \to aX_aAX_bX_bX_b$ and add rules:

• $X_a \to a$,
• $X_b \to b$.