Greibach normal form

Builds on Context-free grammar Context-free language

Definition

Let $G = (N, \Sigma, P, S)$ be a context-free grammar. The grammar $G$ is in Greibach normal form if every rule in $P$ has one of the following forms:

$A \to a A_1 A_2 \cdots A_k$ , where $A \in N$ , $a \in \Sigma$ , $k \ge 0$ and $A_1, \dots, A_k \in N$ ;
$S \to \varepsilon$ , allowed only if $S$ does not occur on the right side of any rule.

Remarks

Example: the rules $S \to aSB$ , $S \to aB$ , $B \to b$ form a grammar in Greibach normal form. Each right side is one terminal followed by nonterminals ( $SB$ , $B$ , or nothing), so clause 1 holds; it generates $\set{a^n b^n : n \ge 1}$ . Non-example: the rule $S \to Sa$ fails clause 1, because its right side starts with a nonterminal; such a rule is called left-recursive. Every context-free language is generated by a grammar in Greibach normal form. In such a grammar, a word of length $n \ge 1$ has derivations of exactly $n$ steps.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`F95BZ9QHS9`
URI	`m2://F95BZ9QHS9`
Kind	definition
Writing	W0 stub
MSC	68Q42, 68Q45
Defines	Greibach normal form
Uses	Context-free grammar, Context-free language
Changed	3 November 2026

Greibach normal form

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here