Convert the grammar into Greibach normal form S -> AB|SA|a A-> SS|d B-> BA|b|c S
ID: 3633497 • Letter: C
Question
Convert the grammar into Greibach normal formS -> AB|SA|a
A-> SS|d
B-> BA|b|c
Explanation / Answer
Hi, S -> ASA | aB A -> B | S B -> b | eps your CNF grammar should be S -> AS | SA | CB | a A-> b | AS | SA | CB | a B -> b C -> a ************************************************************************************************** Saw this online and decided to give another version, because I'm not sure if the answer above is correct. Unless there is a rule that allows ASA -> AS | SA that I don't know about. (From where you left off...) S -> ASA | aB A -> B | S B -> b | eps (Step 1: remove eps productions) S -> ASA | aB | a A -> B | S B -> b (Step 2: remove unit productions) S -> ASA | aB | a A -> b | ASA | aB | a B -> b (Step 3: remove useless productions) none, all have terminal variable (Step 4: put into Chomsky form) S -> DA | CB | a A -> b | DA | CB | a B -> b C -> a D -> AS