Homework SourseI need help on this question Please provide a clear explaina
I need help on this question. Please provide a clear explaination in the solution. Thank you!
Eliminate unit productions from the following context-free grammar: S rightarrow B|SB|ab A rightarrow a|SA B rightarrow A|SB|bSolution
Select a unit production X -> Y, such that production X -> exists, where is a terminal
For every non-unit production, Y -> repeat the following step
Solution:
B -> A and S -> B are the unit productions in the given CFG.
we have A -> a | SA,
To remove B -> A, add the production B -> a | SA to the grammar and remove B - > A production.
B -> SB | b | a | SA
To remove S -> B, add the production S - > SB | b | a | SA to the grammar and remove S -> A production.
S -> SB | b | a | SA | ab
The total productions are
S -> a | b | ab | SA | SB
A -> a | SA
B -> a | b | SA | SB
