Convert Right-Linear Grammar to FA
Definition
How
to Convert Right-Linear Grammar to Finite Automaton (FA)
A right-linear grammar is a special type of regular grammar, in which all productions of G must have at most one variable in the right-hand side, and this variable must be to the right of any terminals.
Using JFLAP, we will show how to convert a right-linear grammar to a finite automaton.
We will begin by loading the grammar. You can either enter the grammar (shown below) or load the file regGrammarToNFA.jff.
Now click on Convert and then Convert Right-Linear Grammar to FA. Your window should look like this after entering Convert to FA mode. Each variable from the grammar is shown as a label for a state, with the start variable the label for the start state. In addition, there is one final state not associated with a variable.
Now, we need to add transitions to finish the FA. When we expand the production “S->aB”, it is similar to reading “a” in state S and moving to state B. Thus, we should create a transition from state S to state B with the transition “a”. After we create that transition on JFLAP, your window should look like this :
*NOTE : For a tutorial on how to use the FA panel, you should first read the tutorial pages on finite automata.
For productions that have no variable on the right-side, a transition is created that goes to the final state. You can check how many transitions you need to add by clicking the Done? button. Finish entering the transitions. JFLAP will notify you which productions are successfully created in the FA. You can also let JFLAP automatically fill in the transitions by clicking the Show All button. When you finish entering all the transitions into FA, your window should look like :
*NOTE : We moved the states in the FA to produce a better picture.
Now, since all the transitions are added, we have successfully transformed right-linear grammar to finite automaton. You can export this FA. When you export the converted FA, the new Finite Automaton window will pop up with the created FA states and transitions. After exporting the FA, your Finite Automaton window would look like this :
This concludes our brief tutorial on Converting Right-Linear Grammar to FA. Thanks for reading!