Greibach normal form conversion

1.1k Views Asked by At

I'm trying to convert this into GNF:

$S \rightarrow ASaa | bab$

$A \rightarrow Ba | bAB$

$B \rightarrow abba$

So I'm getting this, but I'm not sure understanding and applying correctly the concept of where exactly the variables and terminals should be in this format:

$S \rightarrow a A_0 S_0 | b A B S_0 | b S_2$

$S_0 \rightarrow a S_1$

$S_1 \rightarrow a$

$S_2 \rightarrow a S_3$

$S_3 \rightarrow b$

$A \rightarrow a A_0 | b A B$

$A_0 \rightarrow b A_1$

$A_1 \rightarrow b A_2$

$A_2 \rightarrow a A_3$

$A_3 \rightarrow a$

$B \rightarrow a B_0$

$B_0 \rightarrow b B_1$

$B_1 \rightarrow b a$

I'm not sure if I was getting off-track on the $A$ productions, maybe someone can show me where I'm misunderstanding.

1

There are 1 best solutions below

0
On BEST ANSWER

I browsed your productions, and they looked to represent the original grammar, and definitely were in GNF. I am afraid that you complicated matters a little.

First let me note that the original grammar is not too complicated. When there are left-recursive productions like $X\to X\alpha$ then you have to apply more involved constructions, but here we basically work bottom-up.

First but two productions in place that will derive single letters.

$X\to a$, $Y\to b$

Now replace the $B$ production by its GNF equivalent. Single terminals are replaced by these new non-terminal helpers.

$B \to aYYX$

Now the $A$ production. For $A\to BA$ we first substitute a $B$-production to get a terminal in first position.

$A \to aYYXX \mid bAB$

Same trick for $S$, but there are two options for the substitution.

$S \to aYYXXSXX \mid bABSXX \mid bXY$

Now there is a big change a made a copy-past error somewhere, but I hope you see my solution.