🔹 Definition
A context-free grammar is said to be in Greibach Normal Form (GNF) if all productions have the form:
where
That means: every production starts with a terminal, followed optionally by nonterminals.
🔹 Comparison with other normal forms
-
Chomsky Normal Form (CNF): Right-hand side is either two variables () or a single terminal ().
-
Greibach Normal Form (GNF): Right-hand side must begin with a terminal, then zero or more variables.
👉 So CNF is binary-variable structured, while GNF is terminal-first structured.
🔹 Why GNF is important (speciality)
-
Every context-free language (without λ) has an equivalent grammar in GNF.
-
Useful in top-down parsing because the derivation always produces a terminal as the next symbol.
-
Plays a role in proving equivalence of PDA and CFG.
-
Basis for algorithms in parsing theory (important in compiler construction).
🔹 Example
Suppose we have the grammar:
S→AB∣bA→a
B→b
This grammar is not in GNF because productions like start with a nonterminal.
Step 1: Ensure no left recursion and no unit productions
Here, no left recursion and no unit-productions except and (which are fine).
Step 2: Convert rules into GNF form
But since , substitute:
Now all productions start with a terminal:
S→aB∣b A→a
B→b
✅ This is in Greibach Normal Form
Given grammar Find the GNF
S → A B
A → a A | b B | b
B → b
Step — substitute productions of A into S
S → A B — since each production for A begins with a terminal, replace A by its alternatives:
A → a A gives S → a A B
A → b B gives S → b B B
A → b gives S → b B
So S becomes:
S → a A B | b B B | b B
Check all productions
Now list the grammar:
S → a A B | b B B | b B
A → a A | b B | b
B → b
Each production is of the form Nonterminal → terminal (possibly followed by non terminals).That is exactly the Greibach Normal Form requirement (A → a X1 X2 ... Xk, with a a terminal and Xi nonterminals). No production begins with a nonterminal, and there are no ε- or unit-productions in the original grammar, so no further steps are required.
Example
Convert S→a b S b ∣ a a
into Greibach Normal Form (GNF)
(every production must begin with a terminal, followed by zero or more nonterminals).
Step 1 — eliminate terminals that appear after the first position GNF requires that after the initial terminal only nonterminals may appear.Both productions have terminals in positions after the first a:
a b S b has terminals b at positions 2 and 4.
a a has terminal a at position 2.
Introduce new nonterminals that generate single terminals:
X_a → a
X_b → b
Replace each occurrence of a or b that is not the leading a by the corresponding new nonterminal.
Step 2 — rewrite productions using the new nonterminals
S → a b S b becomes S → a X_b S X_b.
(the leading a stays a terminal; the later b's are replaced by X_b)
S → a a becomes S → a X_a.
So the grammar now is:
S → a X_b S X_b | a X_a
X_a → a
X_b → b
Check GNF condition
Each production is of the form A → a α where a is a terminal and α is a (possibly empty) string of nonterminals:
S → a X_b S X_b : terminal a then nonterminals X_b S X_b. ✅
S → a X_a : terminal a then nonterminal X_a. ✅
X_a → a and X_b → b : a single terminal. ✅
Thus the grammar is in Greibach Normal Form.
Comments
Post a Comment