Grammar Design via Regex: Build a Regular Grammar Step by Step

You may understand what a regular expression denotes and still freeze when asked to turn that language into productions without generating extra strings. One reliable method is to move from the regex to a finite automaton, create one nonterminal per state, and copy every transition into a right-linear production. We will apply it to (a|b)*abb, derive one accepted string, reject a near miss, and finish with an exam-ready checking method.

This construction belongs to the wider set of topics collected under CS Fundamentals.

What grammar design via regex must preserve

For a regex R over alphabet Sigma, the goal is to construct a regular grammar G = (V, Sigma, P, S) such that L(G) = L(R). Different variable names can be correct. What matters is equality of the two languages.

We will use only the strict right-linear forms X -> aY, X -> a, and X -> epsilon, where a is a terminal and X and Y are nonterminals. Left-linear grammars are also regular, but mixing left-linear and right-linear orientations inside one construction can change the language.

The start nonterminal represents the automaton's start state. A rule X -> aY consumes exactly a and moves to the state represented by Y. A rule X -> epsilon says that the derivation may stop because the corresponding state is accepting. Review the language operations in Regular Expressions and Pumping Lemma: Worked Proof if union, concatenation, or star needs a refresh.

Read the regex, then build the four-state DFA

Take R = (a|b)*abb over Sigma = {a,b}. The initial star permits any prefix, but the final abb is compulsory. Therefore, a string is accepted exactly when its last three symbols are abb. Strings abb, aabb, and babb belong to the language. Strings epsilon, ab, abab, and abba do not.

If the automaton bridge is unfamiliar, review Finite Automata: DFA vs NFA before building the state table.

Build states from the longest suffix read so far that is also a prefix of abb:

Here, q0 is the start state and q3 is the only accepting state. Two fallback transitions deserve attention. After reading aba, the longest useful suffix is a, so q2 --a--> q1. After reading abbb, no non-empty suffix is a prefix of abb, so q3 --b--> q0.

Translate every DFA row into right-linear productions

Map the states as q0 <-> S, q1 <-> A, q2 <-> B, and q3 <-> C. For every transition qi --x--> qj, add Xi -> xXj. For every accepting state, add Xi -> epsilon.

Copying all eight transitions gives the finished grammar:

• S -> aA | bS

• A -> aA | bB

• B -> aA | bC

• C -> aA | bS | epsilon

The start symbol is S, and the terminal alphabet is {a,b}. Add C -> epsilon because q3 accepts. Do not add S -> epsilon, since q0 is not accepting and the original regex does not accept the empty string. Also keep both outgoing rules from C. An accepting state may stop, but it may instead consume more symbols and accept later, as abbabb requires.

Fully worked verification: derive baabb, reject abab

First trace the accepted string baabb through the DFA:

q0 --b--> q0 --a--> q1 --a--> q1 --b--> q2 --b--> q3

Now mirror those five consumed terminals in the grammar:

S => bS => baA => baaA => baabB => baabbC => baabb

The final step uses C -> epsilon. Both representations finish at the mapped accepting pair after all five symbols.

Now run the near miss abab completely:

q0 --a--> q1 --b--> q2 --a--> q1 --b--> q2

State q2 is not accepting. The grammar reaches the matching result:

S => aA => abB => abaA => ababB

The input is exhausted, but B cannot disappear because it has no epsilon production. Therefore, abab has no terminal-only derivation.

Two cross-checks support the result. The shortest accepted string follows S => aA => abB => abbC => abb. By contrast, abba takes the DFA through q0 -> q1 -> q2 -> q3 -> q1, so it finishes outside q3 and is rejected. Samples test the construction, but the invariant below proves language equality.

Direct shortcuts for tiny regexes

For very small expressions, a direct grammar may be quicker:

• For a|b, use S -> a | b.

• For a*, use S -> aS | epsilon.

• For ab*, use S -> aA and A -> bA | epsilon.

• For (ab)*, use S -> aA | epsilon and A -> bS.

Test the non-trivial cases rather than trusting their appearance. For ab*, the string abbb follows S => aA => abA => abbA => abbbA => abbb. It cannot generate b because every derivation must begin with a. For (ab)*, abab follows S => aA => abS => abaA => ababS => abab, while epsilon follows directly from the start rule.

Some definitions permit the shorthand S -> abS | epsilon. If a question expects one terminal per production, the two-rule form with A is safer. For nested union, concatenation, and star, use the automaton bridge so that every production can be audited against one transition.

Why the conversion works beyond sample strings

The key invariant works in both directions: there is a DFA path from q0 to qi labelled w if and only if the grammar can derive S =>* wXi, where Xi represents qi. Each DFA transition consumes one terminal, and its corresponding grammar production generates that same terminal before moving to the matching nonterminal.

A string w is accepted exactly when its path ends in an accepting state. Only the nonterminals mapped to accepting states receive epsilon productions, so exactly those derivations can remove their final variable and become terminal strings. Here the only accepting pair is q3 <-> C. Therefore, the grammar derives precisely the strings ending in abb.

The same state-to-nonterminal idea also handles nondeterministic transitions by creating alternative rules. An epsilon-NFA needs epsilon-transition handling or prior elimination. An automaton epsilon edge must never be treated as though it consumes an alphabet symbol called epsilon.

How exam questions probe the method

Questions can ask you to select the grammar matching a regex, fill a missing production from a transition table, decide whether a string has a terminal derivation, recover the language of a supplied grammar, or spot mixed left-linear and right-linear rules. Use Regex and FA Equivalence MCQs: 10 Solved PYQs as a follow-on drill after you can perform the conversion unaided.

Remove these common traps:

• The regex contains a star, so add S -> epsilon -> The full regex (a|b)*abb still rejects epsilon.

• q3 is accepting, so it has no outgoing rules -> Keep C -> aA | bS as well as C -> epsilon.

• q2 --b--> q3 gives C -> bB -> The correct direction is B -> bC.

• Four samples match, so equality is proved -> Use the path and derivation invariant.

• S -> aA mixed with A -> Bb -> Keep every nonterminal consistently on the right in this construction.

There are 20+ published practice questions tagged to grammar design via regex, providing a useful revision pool.

The short version and the next study step

Remember five moves: read the regex language, build a finite automaton, map every state to one nonterminal, turn qi --x--> qj into Xi -> xXj, and add epsilon only to accepting-state variables. For (a|b)*abb, only q3 <-> C accepts, so only C can vanish. The trace for baabb ends at q3, while abab ends at q2.

Continue with Theory Of Computation / Automata Theory for focused study. Choose Zero to Hero: Complete CS Course only if you are rebuilding several CS subjects. Reconstruct the four grammar rows without looking, then test abbabb and abba before opening the practice pool.