Question

2. Convert the following grammar to a left-linear grammar. Show your work. S A B + aaS|A|B → bbA|A + bbb B|6

Answer 1

A grammar is said to be left linear grammar if it is in the form of V -> VT^* or V -> T^* where V is called variable and T is called terminal

S -> Saa | A | B

A -> Abb | λ

B -> Bbbb | b

The productions S-> A, S -> B are not in left linear grammar form so convert them

S -> Saa | Abb | Bbbb

A -> Abb | λ

B -> Bbbb | b

The grammar is in left linear form but it has null production so we have to eliminate it

S -> Saa | Abb | Bbbb | bb

A -> Abb | bb

B -> Bbbb | b

Hence this is the grammar in left linear form without null productions