JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Greibach Normal Form

Chomsky normal form made every rule build two variables at a time; Greibach normal form makes every rule start with a terminal. That one shape kills left recursion, guarantees progress, and turns a grammar into a pushdown automaton that reads one letter per move.

A different shape, a different promise

You have just met Chomsky normal form (CNF), where every rule is either A → BC (two variables) or A → a (one terminal), and you saw its payoff: every parse tree becomes binary, derivations have a fixed length, and that fuels both the CYK parsing algorithm and the context-free pumping lemma. Greibach normal form (GNF) is a sibling — another standardized shape for the same context-free grammar — but it makes a completely different promise. In GNF, every rule has the form A → a α, where `a` is a single terminal and α (alpha) is a string of zero or more variables (nonterminals). The right-hand side always starts with one real letter, then optionally some variables.

Look hard at that shape, because the whole guide flows from it. The first symbol you produce is always a terminal — never a variable. So the very moment you apply any rule, you have irrevocably committed one more letter of the output. Contrast CNF: a rule A → BC produces no terminal at all, just two more things to expand. GNF refuses to ever stall on pure bookkeeping; it makes you spend a letter on every single step.

Why a leading terminal is worth so much

Here is the first reason GNF matters: it makes top-down parsing simple and honest. Imagine you are reading an input left to right and trying to build a leftmost derivation — always expanding the leftmost variable. With a GNF grammar, expanding any variable immediately emits a terminal. You can simply check: does that terminal match the next input letter? If yes, consume it and continue; if no, that rule was the wrong guess. Every step both consumes input and makes a choice, so the parse can never spin in place.

The deeper reason is the deadly enemy of all top-down parsing: left recursion. A rule like E → E + T expands E into something that still starts with E. A naive top-down parser, trying to expand E, would expand it to E again, then again, descending forever without ever reading a letter — an infinite loop that consumes no input. GNF is structurally immune to this. Because every right-hand side begins with a terminal, no derivation can ever produce a variable as its leftmost symbol after one step. Left recursion is not merely discouraged in GNF; it is impossible to even write down.

GNF and the pushdown automaton

GNF also gives the cleanest possible bridge to the pushdown automaton (PDA) — the finite-state machine with a stack of plates where you only ever touch the top plate. Recall from the equivalence of grammars and PDAs that a grammar can be simulated by a PDA that keeps the as-yet-unexpanded part of a leftmost derivation on its stack. With an arbitrary grammar, a single PDA move might just rewrite stack symbols without reading any input. GNF makes the simulation tight: because every rule emits exactly one terminal first, the PDA can read exactly one input letter on every move.

Here is the trick spelled out. Build a PDA with a single control state. To process a rule A → a α: when the top of the stack is the variable A and the next input letter is `a`, the machine pops A, consumes `a`, and pushes the variables of α (in reverse, so the first variable ends up on top). Each move reads one letter and replaces A with the rest of what that rule promised. The input is accepted when the stack empties exactly as the input runs out. Because reading and stack-work happen together on every move, a GNF grammar of n rules turns into a PDA in a wonderfully mechanical way.

A GNF grammar for { a^n b^n : n >= 1 }, then a stack trace on 'aabb'

  S -> a S B   |   a B
  B -> b

(every right side starts with a terminal: 'a' or 'b')

Leftmost derivation of aabb:

  S
  => a S B        (S -> a S B)        ate 'a'   stack: S B
  => a a B B      (S -> a B)          ate 'a'   stack: B B
  => a a b B      (B -> b)            ate 'b'   stack: B
  => a a b b      (B -> b)            ate 'b'   stack: (empty) -> ACCEPT

Every single step consumed exactly one input letter -- that is the GNF guarantee.
A tiny GNF grammar and a leftmost derivation that doubles as a PDA run: one terminal consumed per step, the stack mirroring the unexpanded variables.

How the conversion works (the idea)

You do not have to memorize the full algorithm to climb this ladder, but the shape of it is worth seeing. The standard construction starts from a grammar already in Chomsky normal form, orders the variables A1, A2, ..., Ak, and then forces a one-way flow: it rewrites the rules so that whenever a rule's right-hand side begins with a variable, that variable has a higher index than the rule's left side. Once every rule begins with either a terminal or a higher-numbered variable, the highest-numbered variables already start with terminals, and you substitute backwards to push terminals to the front of everyone else.

  1. Clean and convert: remove useless symbols, epsilon-productions, and unit productions in the right order, then put the grammar in Chomsky normal form, so every rule is A → BC or A → a.
  2. Number the variables A1, ..., Ak in any fixed order, and rewrite rules until every rule whose right-hand side starts with a variable starts with a HIGHER-numbered variable — this is exactly removing left recursion, often by introducing fresh helper variables.
  3. Substitute backwards: the highest-numbered variable can only start with a terminal already; plug its rules into the second-highest, and so on down to A1, until every rule begins with a terminal.
  4. Clean up the helper variables the same way, substituting their terminal-leading rules in, so the entire grammar ends in A → a α form.

Notice that step 2 — making variables only ever point to higher-numbered variables — is the engine that destroys left recursion, and it is exactly the left-recursion-removal technique you will study in detail next. The substitution in steps 3 and 4 is where the leading terminals appear. The two normal forms are not rivals; CNF is usually the launchpad from which you reach GNF.

The honest costs

Now the warnings, because GNF is not free. The conversion can cause a real grammar blow-up: substituting one variable's rules into another multiplies their alternatives together, so a grammar with v variables can balloon in the number of rules — the standard construction can produce on the order of v^3 or worse new productions. The pretty A → a α shape can sit on top of a much larger rule set than you started with. Smallness and tidiness pull in opposite directions.

More importantly, the conversion changes the parse trees. The string you accept is the same — the language is unchanged, which is the whole point of a normal form — but the structure GNF assigns to a string usually bears no resemblance to the structure your original, meaningful grammar gave it. The fresh helper variables and rearranged rules mean a GNF parse tree is great for proving a string is in the language efficiently, but useless as the parse tree you would hand to a compiler that cares about precedence and associativity. Use GNF as a theoretical and parsing tool, not as the grammar you author by hand.

Finally, the existence theorem itself is the real prize, even when you never run the algorithm: every context-free language without epsilon has a Greibach normal form grammar. That single fact is what lets theorists assume any CFL can be matched by a PDA reading one letter per move, and it is the cleanest way to prove that grammars and PDAs describe exactly the same class of languages. The shape is a convenience; the guarantee that the shape always exists is the theorem.