Theory of Computation – Regular Grammars

If all production of a CFG are of the form A -> wB or A -> w, where A and B are variables and w ϵ Vt*, then we say that grammar is right linear. If all production of a CFG are of the form A -> Bw or A -> w, we call it left linear. A right or left linear grammar is called a regular grammar.
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:

  1. 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.
  2. The transitions for automata are obtained as follows
    1. For every production A -> aB make δ(A, a) = B that is make an are labeled ‘a’ from A to B.
    2. For every production A -> a make δ(A, a) = final state.
    3. 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

The automaton will have 3 states S, A, F
For production S -> 0S, S -> 1A, S -> 1

For production A -> 0A, A -> 1A, A -> 0, A -> 1.

Question: Consider the regular grammar G = (Vn, Vt, P, S), where Vn = {A, B, S}, Vt = {a, b} and P is defined as
S -> abA
S ->B
S -> baB
S -> ϵ
A -> bS
B -> aS
A -> b
Construct a NFA M such that L(M) = L(G).

The NFA M is


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.

Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn