Regular Grammar and Finite Automata Explained: Conversion, Worked Example and Exam Traps

A regular grammar and a finite automaton can look like two unrelated representations, which makes a conversion question feel harder than it is. The connection becomes simple once each production is read as one labelled transition. We will carry one exact grammar through an NFA and a DFA, then expose the traps that quietly change the language, within the wider CS fundamentals learning path.

Related reading: regular grammar MCQs and DFA construction.

What makes a grammar regular

A grammar is written as G = (V, Sigma, P, S). Here, V is the finite set of non-terminals, Sigma is the terminal alphabet, P is the set of productions, and S is the start symbol.

A right-linear grammar uses rules of these forms:

• A -> aB

• A -> a

• A -> epsilon

A left-linear grammar instead uses A -> Ba, A -> a, and A -> epsilon, where A, B belong to V and a belongs to Sigma. The direction must be consistent across the grammar. A set that mixes right-linear and left-linear non-terminal-bearing rules is not classified as regular merely because each rule looks linear by itself.

Keep three related ideas separate. A regular grammar generates strings, a regular expression denotes a language, and a finite automaton recognises strings. They are different notations with the same language power. The connection with regular expressions and the pumping lemma is useful, but no pumping argument is needed for the conversions here.

Read right-linear productions as automaton moves

For a right-linear grammar, create one automaton state for every non-terminal. The state corresponding to the start symbol becomes the start state. Then translate each production mechanically:

• A -> aB becomes qA -a-> qB.

• A -> a becomes qA -a-> qF, where qF is a new accepting state.

• A -> epsilon makes qA an accepting state.

If two productions leave the same non-terminal on the same terminal, keep both destinations. That is ordinary NFA nondeterminism.

This construction preserves the language because each production consumes exactly one input symbol. The current non-terminal records the current state, and a completed derivation corresponds to a path that consumes the entire string and ends in an accepting state. Finite automata and regular grammars cover regular languages. General context-free behaviour, such as arbitrary nesting, needs stack memory.

Worked example: convert one regular grammar to an NFA

Consider the grammar:

G = ({S, A}, {0, 1}, P, S)
P:
S -> 0S | 1S | 0A
A -> 1

Every production is right-linear. Create states qS, qA, and a new accepting state qF. The start state is qS, and the accepting set is {qF}.

The complete transition function is:

Now derive 1101 in the grammar:

S => 1S => 11S => 110A => 1101

The matching NFA state-set trace is:

{qS} -1-> {qS} -1-> {qS} -0-> {qS,qA} -1-> {qS,qF}

The input is accepted because qF is present after all four symbols have been consumed. For 1110, the trace is:

{qS} -1-> {qS} -1-> {qS} -1-> {qS} -0-> {qS,qA}

The input has ended without qF, so it is rejected. Therefore,

L = {w01 | w in {0,1}*}

This is the set of all binary strings ending in 01. The shortest member, 01, is accepted. The strings epsilon, 1, and 010 are rejected.

Determinise the NFA without changing its language

Subset construction turns each reachable NFA state set into one DFA state:

• D0 = {qS}, the start state

• D1 = {qS,qA}

• D2 = {qS,qF}, the only accepting state

The deterministic transition table is complete:

For 1101, the DFA follows D0 -1-> D0 -1-> D0 -0-> D1 -1-> D2, so it accepts. No empty subset is reachable because every reachable subset contains qS.

These three states cannot be merged. D2 differs from both other states on the empty suffix because only D2 accepts. D0 and D1 differ on suffix 1: D0 -1-> D0 rejects, while D1 -1-> D2 accepts. See DFA, NFA and subset construction for a broader determinisation refresher.

Convert the DFA back to an equivalent regular grammar

Use one non-terminal for each DFA state. Every transition Di -a-> Dj becomes a production Di -> aDj. Since D2 is accepting, add D2 -> epsilon. With D0 as the start symbol, the grammar is:

D0 -> 0D1 | 1D0
D1 -> 0D1 | 1D2
D2 -> 0D1 | 1D0 | epsilon

This grammar does not look identical to the original, but equivalence means both generate the same language. Check 1101:

D0 => 1D0 => 11D0 => 110D1 => 1101D2 => 1101

The last step uses D2 -> epsilon. Stopping at 1101D2 would leave a non-terminal, so it would not yet be a terminal string.

Traps that change the answer

Mixing directions. Consider S -> aA | epsilon and A -> Sb. The rules mix right-linear and left-linear forms. They derive S => aA => aSb => aaAb => aaSbb => ... => a^n S b^n => a^n b^n, producing {a^n b^n | n >= 0}, which is not regular. Check one consistent direction across all rules containing non-terminals.

Mishandling a terminal-only rule. The production A -> 1 is not a loop, and it does not make qA accepting before reading 1. It creates qA -1-> qF. Only A -> epsilon makes the source state accepting immediately.

Following one NFA branch. From qS, input 0 reaches both qS and qA. Track the full state set. Acceptance requires at least one complete branch to finish in qF, and the entire input must be consumed. Merely matching a prefix does not make a state accepting.

How objective questions test regular grammar and FA

Common question formats ask you to identify a regular grammar, infer its language, convert it to an NFA or DFA, trace a string, compare two representations, or decide whether DFA states can be merged.

Use this quick routine:

1. Circle the start symbol.

2. Mark each rule as right, left, terminal-only, or epsilon.

3. When standard regular-grammar forms are being used, reject a mixed direction.

4. Build the labelled transitions and mark accepting states.

5. Trace the complete input as a state set.

6. For DFA conversion, list reachable subsets before considering minimisation.

KnowledgeGate has 10+ published questions tagged to Regular Grammar & FA. Treat that only as a practice-bank availability cue, not as official weightage or evidence about any examination's frequency.

Short version and the next practice step

Remember five rules: keep the linear direction consistent; map non-terminals to states; map A -> aB to a labelled transition; map A -> a through a new final state; and map A -> epsilon by making A's state accepting. Our grammar generates all binary strings ending in 01, and its self-check trace is D0 -1-> D0 -1-> D0 -0-> D1 -1-> D2.

Now rebuild the NFA and its three-row DFA table without looking. Test 01, 101, 1110, and epsilon. Their outcomes are accept, accept, reject, and reject, respectively, because only the first two traces finish in an accepting state after consuming the full input.

For focused Automata Theory study, continue with the Theory Of Computation / Automata Theory course. If you are rebuilding several CS foundations together, the Zero to Hero complete CS course is the broader route.