Greibach Normal Form - GNF

 

🔹 Definition 

A context-free grammar is said to be in Greibach Normal Form (GNF) if all productions have the form:

A    aX1X2XkA \;\to\; aX_1X_2 \cdots X_kwhere
  • AVA \in V (a nonterminal),

  • aTa \in T (a terminal),

  • each XiVX_i \in V, and

  • k0.

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 (ABCA \to BC) or a single terminal (AaA \to a).

  • 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)

  1. Every context-free language (without λ) has an equivalent grammar in GNF.

  2. Useful in top-down parsing because the derivation always produces a terminal as the next symbol.

    • No left recursion issues: at each step, the derivation consumes one input symbol.

  3. Plays a role in proving equivalence of PDA and CFG.

  4. Basis for algorithms in parsing theory (important in compiler construction).


🔹 Example 

Suppose we have the grammar:

S→AB∣bSABb
Aa
Bb

This grammar is not in GNF because productions like SABS \to AB start with a nonterminal.


Step 1: Ensure no left recursion and no unit productions

Here, no left recursion and no unit-productions except AaA \to a and BbB \to b (which are fine).


Step 2: Convert rules into GNF form

  • AaA \to a (already terminal first).

  • BbB \to b is fine.

  • SbS \to b is fine.

  • SABS \to AB: not fine (starts with AA).

But since AaA \to a, substitute:

SAB    SaBS \to AB \implies S \to aB

Now all productions start with a terminal:


S \to aB \mid b \\ A \to a \\ B \to 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

Popular posts from this blog

Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

Non deterministic Finite Automata NFA

Formal Definition - Turing Machine