Find a greibach normal form grammar equivalent to the following CFG S-> ASB /AB A-> a B-> b
Answers
Answer:
G1 = {S->aA|bB, B->bB|b, A->aA|a}
G2 = {S->aA|bB, B->bB|ε, A->aA|ε}
The grammar G1 is in GNF as production rules satisfy the rules specified for GNF. However, the grammar G2 is not in GNF as the production rules B-> ε and A-> ε do not satisfy the rules specified for GNF (only start symbol can generate ε).
Note –
For a given grammar, there can be more than one GNF
GNF produces the same language as generated by CFG
How to convert CFG to GNF –
Explanation:
Step 1. Convert the grammar into CNF.
If the given grammar is not in CNF, convert it to CNF. You can refer following article to convert CFG to CNF: Converting Context Free Grammar to Chomsky Normal Form
Step 2. Eliminate left recursion from grammar if it exists.
If CFG contains left recursion, eliminate them. You can refer following article to eliminate left recursion: Parsing | Set 1 (Introduction, Ambiguity and Parsers)
Step 3. Convert the production rules into GNF form.
If any production rule is not in the GNF form, convert them. Let us take an example to convert CFG to GNF. Consider the given grammar G1:
S → XA|BB
B → b|SB
X → b
A → aAs G1 is already in CNF and there is not left recursion, we can skip step 1and 2 and directly move to step 3.
The production rule B->SB is not in GNF, therefore, we substitute S -> XA|BB in production rule B->SB as:
S → XA|BB
B → b|XAB|BBB
X → b
A → a
The production rules S->XA and B->XAB is not in GNF, therefore, we substitute X->b in production rules S->XA and B->XAB as:
S → bA|BB
B → b|bAB|BBB
X → b
A → a
Removing left recursion (B->BBB), we get:
S → bA|BB
B → bC|bABC
C → BBC| ε
X → b
A → a
Removing null production (C-> ε), we get:
S → bA|BB
B → bC|bABC|b|bAB
C → BBC|BB
X → b
A → a
The production rules S->BB is not in GNF, therefore, we substitute B → bC|bABC|b|bAB in production rules S->BB as:
S → bA| bCB|bABCB|bB|bABB
B → bC|bABC|b|bAB
C → BBC|BB
X → b
A → a