Automata

Conversion of Right Linear Grammar to Finite Automata

Converting right linear grammar to Finite Automata is simple.
Follow the steps:

  1. Start from the first production
  2. And then for every left alphabet go to SYMBOL followed by it
  3. Start State: It will be the first production's state
  4. 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 -> aB/bA/b
			B -> aC/bB
			C -> aA/bC/a

Now see the output and you will understand what just happened.

Explanation

As you can see for state A, transitoin on 'a' is going on state B
And on 'b' it is going on state A itself...
This method will apply to all the states.

Note:Final states are A and C, cause they are having terminal production



Quantitative Aptitude
Reasoning
Programming
Interview