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 forA :

A → aA | aB

Same way we can write production rule forB :

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)