Conversion of Left Linear Grammar to Finite Automata
Converting left linear grammar to Finite Automata is simple.
Follow the steps:
- Take reverse of CFG
- Create Finite automata using privious example
- Then again take reverse of the FA and that will be our final output
- Start State: It will be the first production's state
- Final State: Take those states which end up with input alphabets. eg. State A and C are below CFG
Here we are giving one right linear grammar
A -> Ba/Ab/b B -> Ca/Bb C -> Aa/Cb
We will follow the steps
- Take the reverse of the CFG
- Now create the FA
- Now take reverse of the above FA (this is final output)
A -> aB/bA/b B -> aC/bB C -> aA/bC/a

Note: Only state A is final state in this example

Note: Here state A was itself a final state that is why it again become start state as well as final state.