CREATE OWN LIBRARY

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 ${\mathit{q}}_{\mathbf{0}}$ level as S, ${\mathit{q}}_{\mathbf{1}}$ as A, ${\mathit{q}}_{\mathbf{2}}$ as B, ${\mathit{q}}_{\mathbf{3}}$ as C and ${\mathit{q}}_{\mathbf{4}}$ as D.

Important: ${\mathit{q}}_{\mathbf{3}}$, ${\mathit{q}}_{\mathbf{4}}$ 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}

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:

Grammar:

    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 ${\mathit{n}}_{\mathbf{a}}$(ω) mod 3 = 0 or ${\mathit{n}}_{\mathbf{a}}$ (ω) = 3k (multiple of 3)