Construction of regular grammar from Finite Automata:


Now we can construct a regular grammar from Finite State Machine  (DFA/NFA)

Let's take a Finite State Machine to construct regular grammar


Step 1: 

Initially, we give a level number naming as a grammar variable like S, A, B, etc. to each state. 

Here q0 level as Sq1 as Aq2 as Bq3 as C and q4 as D.


Important: q3q4 here the trap state which not participated to construct regular grammar because the trap state is not a direct part of the machine.  So, state C and D never participated.


Step 2: 

Alphabets (Inputs) used in this machine are {a, b}is considered as terminals of the grammar and level (S, A, B which represent states) use as variables of the grammar.

Now we construct the production of the grammar by moments of levels (S, A, B which represent states) using inputs or terminals.


If we put input a at S we go to S itself so, S → aS. Now if we put input b at S we move to A so, S → bA, and because of S is the final state so, it must have a λ move in that case S → λ.


So, we can write to gather as S → aS | bA | λ

Note: For every final state must have a λ move


Using same method we can write production rule for  A :


A → aA | aB


Same way we can write production rule for  B :


B → aB | bA | λ   (It contains λ because B is final state)


We can write grammar all to gather as:


G = {V , T , S , P}

G ({S,A,B}, {a,b}, {S}, P}


    S → aS | bA | λ 

    A → aA | aB

    B → aB | bA | λ


Construction of Finite machine from grammar:


We can also design a Finite State Machine from a certain grammar. 

Let's take a grammar as an example and convert it to the corresponding machine:



    S → aA | λ | bS 

    A → aB | bA

    B → aS | bB 

We consider all variables (S, A, B) as states and all terminals (a, b) treated as an input of the machine. S is taken as an initial state and variable which contains λ in its production treated as the final state.

This machine is na(ω) mod 3 = 0 or na (ω) = 3k (multiple of 3)