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.

If you find any mistake above, kindly email to [email protected]

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.