Course contentsShow
← Computer Science
Lesson 1844 of 2,87241. Context-Free LanguagesFree lesson

Greibach Normal Form

Understanding GNF where every production starts with a terminal followed by variables.

Greibach Normal Form (GNF)

You'll learn what Greibach Normal Form is and how it structures productions for predictable parsing.


What Is Greibach Normal Form?

Greibach Normal Form (GNF) is a specific way of writing context-free grammar productions where every production starts with a terminal symbol, followed by zero or more variables.

In formal terms, every production has the form:

A → aα

where:

  • A is a variable (non-terminal)
  • a is a terminal (the first symbol must always be a terminal)
  • α is a string of zero or more variables (no terminals allowed here)

Why This Matters

GNF provides a "left-to-right" predictability: when you see a variable A, you know the next symbol in the string must be a terminal. This makes certain parsing algorithms more straightforward and connects nicely to pushdown automata design.

Example

A grammar in GNF might look like:

S → aAB
A → b
B → cC
C → d

Notice: every production's right-hand side begins with a terminal (a, b, c, d), and any symbols following are variables (A, B, C).


Contrast with CNF

You've already seen Chomsky Normal Form, where productions are A → BC or A → a. GNF flips the emphasis: instead of isolating terminals or pairs of variables, it always leads with a terminal, making the "next character to consume" explicit.


Key Takeaway: Greibach Normal Form ensures every production starts with a terminal followed by variables, providing predictable left-to-right structure for parsing and theoretical analysis.