Regular Grammars and Finite Automata Equivalence

1. Defining Regular Grammars

We've seen that CFGs can have production rules of the form A → γ, where γ is any string of variables and terminals. Regular grammars are much more restrictive. Their structure is designed to mirror the step-by-step computation of a finite automaton.

A grammar is considered regular if all of its production rules conform to one of two types: either it is entirely right-linear or entirely left-linear.

As you've just read, the definitions are:

• Right-Linear Grammar: All productions are of the form A → aB or A → a, where A and B are variables and a is a terminal.
• Left-Linear Grammar: All productions are of the form A → Ba or A → a.

The key constraint is that a regular grammar must be one or the other, not a mixture.

Notice the structure of a right-linear rule like A → aB. You can think of this as a computational instruction: "From state A, read the terminal a and transition to state B." Similarly, A → a corresponds to: "From state A, read a and transition to a final (accepting) state." This direct correspondence is the key to proving their equivalence with finite automata.

2. Proof of Equivalence, Part 1: Regular Grammar → NFA

To prove that regular grammars and finite automata are equivalent, we must show we can convert from one to the other. Let's start by constructing a Nondeterministic Finite Automaton (NFA) from a given right-linear grammar.

Theorem: For any right-linear grammar G, there exists an NFA M such that L(G) = L(M).

The construction is a direct mapping of grammar components to automaton components:

1. States (Q): The states of the NFA are the variables of the grammar, plus one new, dedicated final state (let's call it Q_f).
2. Input Alphabet (Σ): The terminals of the grammar.
3. Start State (q_0): The start symbol of the grammar.
4. Final States (F): The set containing only our new state, F = {Q_f}. If the grammar generates ε (i.e., S → ε), the start state S is also a final state.
5. Transition Function (δ):
   • For every production A → aB in the grammar, we add a transition δ(A, a) = B.
   • For every production A → a in the grammar, we add a transition to our new final state: δ(A, a) = Q_f.

The following video provides a clear walkthrough of this procedure with two examples.

This constructive proof shows that any language generated by a right-linear grammar can be recognized by an NFA. Since NFAs recognize regular languages, all languages generated by right-linear grammars are regular.

3. Proof of Equivalence, Part 2: NFA → Regular Grammar

Now, let's prove the other direction: constructing a right-linear grammar from a given finite automaton.

Theorem: For any finite automaton M, there exists a right-linear grammar G such that L(M) = L(G).

This construction is the reverse of the previous one:

1. Variables (V): The states of the automaton.
2. Terminals (T): The input alphabet of the automaton.
3. Start Symbol (S): The start state of the automaton.
4. Productions (P):
   • For every transition δ(Q_i, a) = Q_j, we create a production Q_i → aQ_j.
   • Crucially, if Q_j is a final state, we add a second production Q_i → a. This rule allows a derivation to terminate after entering a final state.
   • If the start state Q_0 is also a final state, we add the production Q_0 → ε to handle the empty string.

Let's see this in action.

4. The Complete Equivalence

We have now demonstrated through constructive algorithms that we can convert any right-linear grammar into an equivalent NFA, and any FA into an equivalent right-linear grammar. This completes the proof of their equivalence.

What about left-linear grammars? A similar proof exists (often by considering the reversal of the language), which shows they are also equivalent to finite automata. Therefore, both right-linear and left-linear grammars generate the class of regular languages.

This result solidifies a major concept in formal language theory. The class of regular languages can be characterized in three equivalent ways:

1. Recognized by a Finite Automaton (DFA/NFA).
2. Described by a Regular Expression.
3. Generated by a Regular Grammar (Right-Linear or Left-Linear).

The following table from the Chomsky Hierarchy places this equivalence in a broader context, showing that Type-3 languages (Regular) are associated with both Regular Grammars and Finite State Machines.

Conclusion

In this lesson, we have formally linked the generative power of grammars with the recognition power of automata at the regular language level. This is a significant milestone in our journey through the theory of computation.

Key Takeaways:

• Regular Grammars are a restricted form of CFGs that are either purely right-linear (A → aB or A → a) or purely left-linear (A → Ba or A → a).
• The structure of a regular grammar production directly mirrors a state transition in a finite automaton.
• We can algorithmically convert between regular grammars and finite automata in both directions, proving their formal equivalence.
• This establishes regular grammars as the third major formalism for the class of regular languages.

Preview of the Next Lesson:
We have now thoroughly examined the regular languages and their formalisms. In the next module, we will climb one step up the Chomsky Hierarchy. We will finally introduce the abstract machine that corresponds to Context-Free Grammars: the Pushdown Automaton (PDA). Unlike finite automata, PDAs have a simple form of memory—a stack—which gives them significantly more computational power.