So far, this course has described regular languages using two different notations: transition diagrams for finite automata, and symbolic patterns for regular expressions. This chapter introduces a third way of describing exactly the same class of languages, this time borrowed from the world of formal grammars, where a language is defined not by a machine or a pattern, but by a set of rewriting rules that generate strings one step at a time.
Grammars might feel like a strange detour if you are used to thinking about automata as machines that read and process input. A grammar works in the opposite direction: instead of reading a string and deciding whether to accept it, a grammar starts from a special symbol and generates strings by repeatedly applying rewriting rules until only symbols from the alphabet remain. Despite this reversed perspective, a regular grammar generates exactly the same class of languages that a finite automaton can recognize, which is precisely why this chapter fits naturally between automata and the broader grammar hierarchy covered in the next chapter.
In this tutorial, you will learn what a formal grammar is, how regular grammars are formally defined, the difference between right-linear and left-linear grammars, how to derive strings from a grammar step by step, and how to construct a regular grammar directly from a finite automaton. Worked examples are included throughout to make each rule concrete.
A formal grammar is a set of rules used to generate strings belonging to a language. Every grammar consists of a set of terminal symbols, which are the actual symbols that appear in the final generated strings, and a set of non-terminal symbols, which act as placeholders that get replaced during the generation process according to the grammar's production rules. One special non-terminal, called the start symbol, marks where every derivation must begin.
Formally, a grammar is defined as a 4-tuple (V, Σ, P, S), where V is the set of non-terminal symbols, Σ is the set of terminal symbols, P is the set of production rules describing how non-terminals can be rewritten, and S is the start symbol, a special member of V.
| Component | Meaning |
|---|---|
| V (Non-terminals) | Placeholder symbols, usually written as uppercase letters, that get replaced during derivation and never appear in a final generated string. |
| Σ (Terminals) | The actual alphabet symbols, usually written in lowercase, that make up the final strings the grammar generates. |
| P (Production Rules) | Rewriting rules describing how a non-terminal can be replaced by a combination of terminals and non-terminals. |
| S (Start Symbol) | The single non-terminal from which every derivation begins. |
Not every grammar produces a regular language. A grammar is classified as regular only if every one of its production rules follows a very restricted format, limiting how terminals and non-terminals can be combined on the right-hand side of each rule. This restriction is exactly what keeps a regular grammar's expressive power equal to that of a finite automaton, no more and no less.
Regular grammars come in two closely related forms, right-linear and left-linear, depending on where the single allowed non-terminal is positioned within each production rule.
In a right-linear grammar, every production rule takes one of two allowed forms: a non-terminal produces a terminal followed by at most one non-terminal, or a non-terminal produces a terminal alone, or the empty string.
Allowed forms: A → aB A → a A → ε
Here, A and B represent non-terminals, and a represents a single terminal symbol. The defining feature is that any non-terminal appearing on the right-hand side must appear at the very end of the rule, after the terminal symbol, which is exactly why this style is called "right-linear."
A left-linear grammar mirrors this structure exactly, except the non-terminal must appear at the very beginning of the rule, before the terminal symbol.
Allowed forms: A → Ba A → a A → ε
Although right-linear and left-linear grammars look structurally different, they generate exactly the same class of languages, namely regular languages. A grammar that mixes right-linear and left-linear rules together, however, is generally not considered a regular grammar, since combining both directions in a single grammar can produce languages beyond what finite automata can recognize.
Consider the following right-linear grammar over the alphabet Σ = { a, b }, designed to generate every string consisting of one or more a symbols followed by exactly one b.
Non-terminals: { S, A }
Terminals: { a, b }
Start symbol: S
Production rules:
S → aA
A → aA
A → b
S → aA (using S → aA) → a aA (using A → aA) → a a aA (using A → aA) → a a a b (using A → b) Final string: aaab
Each step in this derivation replaces exactly one non-terminal according to one of the grammar's production rules, gradually building up the final string until no non-terminals remain. Tracing a derivation like this, one rule at a time, is the most reliable way to convince yourself that a particular string genuinely belongs to the language a grammar describes.
L(G) = { a^n b | n ≥ 1 }
This grammar generates the language of one or more a symbols followed by exactly one b, which can also be described using the regular expression aa*b, connecting this grammar back directly to the notation covered in the previous chapter.
Now consider a left-linear grammar over the same alphabet Σ = { a, b }, designed to generate every string consisting of exactly one b followed by one or more a symbols.
Non-terminals: { S, A }
Terminals: { a, b }
Start symbol: S
Production rules:
S → Aa
A → Aa
A → b
S → Aa (using S → Aa) → Aaa (using A → Aa) → Aaaa (using A → Aa) → baaa (using A → b) Final string: baaa
Notice how, in a left-linear grammar, the non-terminal stays attached to the left side of the growing string throughout the derivation, only being replaced by a terminal symbol at the very last step. This is the structural mirror image of what happened in the right-linear example above, where the non-terminal stayed attached to the right side instead.
Since regular grammars and finite automata are equally powerful, there is a direct, mechanical way to convert any DFA or NFA into an equivalent right-linear grammar. This conversion mirrors the structure of the automaton almost exactly, which makes it one of the easier conversions to perform by hand.
Recall the DFA from an earlier chapter that accepts every string over Σ = { 0, 1 } containing an even number of 1s, with states q0 (start, accepting) and q1.
DFA transitions: q0 --0--> q0 q0 --1--> q1 q1 --0--> q1 q1 --1--> q0
Non-terminals: { Q0, Q1 }
Terminals: { 0, 1 }
Start symbol: Q0
Production rules:
Q0 → 0Q0
Q0 → 1Q1
Q1 → 0Q1
Q1 → 1Q0
Q0 → ε (since q0 is an accepting state)
Every transition in the original DFA becomes a production rule in the new grammar, and the single accepting state contributes the extra rule allowing the derivation to end. This close, almost mechanical correspondence between states and non-terminals is exactly what guarantees the grammar generates precisely the same language the DFA recognizes.
Regular grammars complete a triangle of equivalent notations for regular languages, alongside finite automata and regular expressions. Each notation has its own strengths: automata are ideal for simulation and execution, regular expressions are ideal for compact, human-readable pattern descriptions, and grammars are ideal for describing how a language is generated rather than how it is recognized, a perspective that becomes essential once more powerful grammars are introduced in later chapters.
This generative perspective is particularly important because it sets up a natural bridge to context-free grammars, covered in a later chapter, which relax the strict right-linear or left-linear restriction and are capable of describing far more complex languages, including nested and recursive structures that regular grammars simply cannot express.
| Aspect | Regular Grammar | Regular Expression | Finite Automaton |
|---|---|---|---|
| Perspective | Generates strings using production rules. | Describes strings using a compact symbolic pattern. | Recognizes strings by processing them through states. |
| Best Suited For | Explaining how a language is structurally built. | Quickly writing and matching patterns in text. | Simulating and executing recognition efficiently. |
| Computational Power | Exactly regular languages. | Exactly regular languages. | Exactly regular languages. |
| Mistake | Correct Understanding |
|---|---|
| Mixing right-linear and left-linear rules within a single grammar. | A regular grammar should consistently follow either the right-linear or left-linear format, not both at once. |
| Forgetting to add an ε production for accepting states when converting from an automaton. | Every accepting state in the original automaton must contribute a rule allowing the derivation to terminate. |
| Assuming a grammar always describes exactly one string. | A grammar with recursive production rules, such as A → aA, can generate infinitely many strings, not just one. |
| Confusing terminals with non-terminals in a derivation. | Only non-terminals can be replaced during a derivation; terminals are final symbols that remain unchanged once introduced. |
Regular grammars offer a third equivalent way of describing regular languages, this time through the lens of string generation rather than string recognition. By restricting production rules to a strict right-linear or left-linear format, these grammars remain exactly as powerful as finite automata and regular expressions, no more and no less, and can be mechanically converted back and forth between all three notations.
In this tutorial, you learned the formal definition of a grammar, the distinction between right-linear and left-linear regular grammars, how to derive strings step by step from a grammar's production rules, and how to construct a regular grammar directly from an existing finite automaton. With this foundation, you are ready to move on to the pumping lemma for regular languages, a powerful tool used to formally prove that certain languages fall outside the reach of any regular grammar, regular expression, or finite automaton.