How does one convert a regular grammar into a finite automaton (FA)? For instance, what would a finite automaton corresponding to the following regular grammar look like?
VN = {S, B, D} (nonterminals) VT = {a, b, c} (terminals) P = {S -> aB, S -> bB, B -> bD, D -> b, D -> aD, B -> cB, B -> aS} (productions) The good news is that this is not too hard. The idea is that each of the nonterminals will become a state in a nondeterministic finite automaton accepting the language of the grammar, and productions will become transitions. Our NFA will have states S, B and D, and will transition among those states according to the production rules. Our NFA looks like this:
___a__ _a_ / \ / \ | | \ / V | \ / ----->S-a,b->B--b-->D / \ / \ \_c_/ There was one dangling production D -> b which we haven't added yet. We need to introduce another state, not corresponding to an nonterminal symbol, to allow us to transition from D on b and accept some strings:
___a__ _a_ / \ / \ | | \ / V | \ / ----->S-a,b->B--b-->D--b-->Q / \ / \ \_c_/ Now if we make S the initial state and Q the accepting state, we have an NFA that works. If we want a DFA, we might notice that this FA is only nondeterministic because we are lacking required transitions from states S, D and Q. We can add the missing transitions by introducing a new dead state X which will keep track of the NFA we just derived having crashed at some point during its processing:
___a__ _a_ / \ / \ | | \ / V | \ / ----->S-a,b->B--b-->D--b-->Q | / \ | | | / \ | | a,b,c c \_c_/ c a,b,c / \ | | | \ / V V V \ / +-------------+------+----->X