Every regular expression can be represented by a regular grammar. As there is a finite automaton for every regular expression we can generate a finite automaton for the regular grammar.
Conversion of Regular Grammar into Finite Automata
Given a regular grammar G, a finite automata accepting L(G) can be obtained as follows:
- The number of states in the automata will be equal to the number of non-terminals plus one. Each state in automata represents each non-terminal in the regular grammar. The additional state will be the final state of the automata. The state corresponding to the start symbol of the grammar will be the initial state of automata. If L(G) contains ϵ that is start symbol is grammar devices to ϵ, then make start state also as final state.
- The transitions for automata are obtained as follows
- For every production A -> aB make δ(A, a) = B that is make an are labeled ‘a’ from A to B.
- For every production A -> a make δ(A, a) = final state.
- For every production A -> ϵ, make δ(A, ϵ) = A and A will be final state.
Example:Give the automaton for the following grammar:
S -> 0S/1A/1
A -> 0A/1A/0/1
For production S -> 0S, S -> 1A, S -> 1
For production A -> 0A, A -> 1A, A -> 0, A -> 1.
S -> abA
S -> baB
S -> ϵ
A -> bS
B -> aS
A -> b
Construct a NFA M such that L(M) = L(G).
Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.
If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.