Greibach Normal

Form
▪ A context-free grammar is S → aB | bA
in Greibach Normal Form
if the right-hand side of A → a | aS | bAA
each rule has one terminal B → b | bS | aBB
followed by zero or more
non-terminals:

AaX
where
a 
X  V* 1
 Advantages:
● Every derivation of a string s contains |s| rule
applications. So strings can be quickly parsed.
● Greibach normal form grammars can easily be
converted to pushdown automata with no - transitions.
This is useful because such PDAs are guaranteed to
Shalt.
→ aB | bA S  aB # of derivation
A → a | aS | bAA  aaBB steps = |aababb|
B → b | bS | aBB  aabSB =6
 aabaBB
 aababB
Derive the string
 aababb
aababb

2
 Conversion to Greibach Normal Form using
substitution
S → aBc S → aBC S → Bc S → bC
B→b B→b B→b C→c
C→c
S  AB S  aAB | bBB |
A  aA | bB | b bB
Bb A  aA | bB | b S  AB
Bb A  BS | b
S → aABSB | aA B  SA | a
S → aabSb | aa
B→b
A→a
3
To convert a CFG in to a GNF:

1. the grammar has to be in

Chomsky Normal Form

2. there should be no Left-

Recursive Rules

4
But first we need to understand the concept of
Left – Recursive Rules
This is a left-recursive rule: Ak → Akα | β
The alternative (β) allows a derivation to “break out of”
the recursion.
Every left-recursive rule must have an alternative (β)
that allows breaking out of the recursion.
The rule Ak → Akα | β generates the language: βαn, n≥0
To see this, look at a few derivations:

5
 Eliminate left-recursion
• We want to eliminate the left-recursion in
this rule: Ak → Akα | β
• And we know the rule produces βαn
• But the language can also be generated
using these rules:
Ak →β|βZ
Z → α Z| α
• With those two rules we have eliminated the
left recursion.

6
Multiple left-recursive alternatives

 Ak may have multiple alternatives that are left-

recursive:
Ak → Akα1 | Akα2 | … | Akαr
 And Ak may have multiple other alternatives:
Ak → β1 | β2 | … | βs
 So Ak may generate following strings where
X = {α1,…,αr}+:
 β1X
 …
7
₪ The prodns with no left recursion are same as in P
₪ Let Zk be a new variable
₪ Let G1 = (V  {Zk}), Σ, P1, S) where P1 is defined as
 The set of Ak prodns in P1 are

Ak → β1 | β2 | … | βs
Ak → β1 Zk | β2 Zk | … | βs Zk
 The set of Z prodns in P1 are

Z k → α1 Z k | α2 Z k | … | αr Z k
Z k → α1 | α2 | … | αr
8
Loop
Convert to GNF
Convert to GNF A1  A 2 A 3
A1  A 2 A 3 A2  A 3 A 3
A2  A 3 A 3 A3  A 2 A 3 | a
A3  a A 3 | a There is a LOOP
Using substitution, we A2  A3  A2
can easily convert to
GNF Which gives rise to
Left recursion when we
A1  a A 3 A3 A 3 | a A3 A3 do substitution
A2  a A 3 A 3 | a A 3 A2  A 2 A3 A 3 | a A3
9
 Conversion to GNF

1. Eliminate null, unit productions &

useless symbols from the grammar G
2. Convert it to Chomsky Normal Form
(CNF) generating the language L(G′ ) =
L(G) − {ε} where
G′ = (V′ , Σ, P′ , S) in.
3. Rename the variables like A1, A2, . . .
An
starting with S = A1. Rewrite the 10
4. Checking for loop
◊ Prodns of following form don’t give rise to
loops
Ai  a X where a  Σ, X (V  Σ)*
Ai  Aj X where X (V  Σ)* and i < j
◊ In prodns having loop, carry out substitution to
get Left Recursion.
Ai  Aj X where X (V  Σ)* and i > j
5. Eliminate Left Recursion from all the Prodns
6. Do substitution in prodns not in GNF
11
Convert to GNF
Step 4: Check for Loop
S  AB A3  A1 A2 // i > j
A  BS | b
A3  A2 A3 A2 // i > j
B  SA | a
A3  A3 A1 A3 A2 | b A 3 A2
Step 1 & 2: Convert to
CNF Step 5: Eliminate Left
Already in CNF Recursion
A1  A2 A3
Step 3: Rename the A2  A3 A1 | b
variables & Rewrite the
prodns A3  A3 A1 A3 A2 | b A 3 A2 | a

S – A1 A – A2 B–
12

A3
A3  A3 A1 A3 A2 | b A3 A2 |
a A prodns are:
A3  b A 3 A2 | a
A 3  b A 3 A 2 Z3 | a Z 3

’s & 1 β1 Z prodns are:

β β’s ??
2 Z3  A 1 A 3 A 2 Z3
Z3  A 1 A 3 A 2

13
5. Step 6: Do
All A3 prodns are in GNF
substitution in
prodns not in GNF A 3  b A 3 A 2 | b A 3 A 2 Z3 | a Z 3 | a
14
A1  A2 A3
A2  A3 A1 | b Substitute in A2  A3 A1 | b
A3  b A 3 A2 | a So we get 5 A2 prodns
A 3  b A 3 A 2 Z3 | a Z 3 Substitute in A1  A2 A3
Z3  A 1 A 3 A 2 Z3 So we get 5 A1 prodns
Z3  A 1 A 3 A 2 Substitute in Z3  A1 A3 A2 Z3 | A1
Total 24 A3 A2
prodns So we get 5 + 5 Z3 prodns
 Substitute in A2  A3 A1 | b
5. Step 6: Do
substitution in A 2  b A 3 A 2 A 1 | b A 3 A 2 Z3 A 1 | a
prodns not in GNF Z3 A 1 | a A 1 | b

A1  A2 A3 Substitute in A1  A2 A3

A2  A3 A1 | b A 1  b A 3 A 2 A 1 A 3 | b A 3 A 2 Z3 A 1 A 3
| a Z3 A1 A3 | a A 1 A3 | b A 3
A3  b A 3 A2 | a
Substitute in Z3  A1 A3 A2 Z3
A 3  b A 3 A 2 Z3 | a Z 3
Z3  b A 3 A 2 A 1 A 3 A 3 A 2 Z3 | b A 3 A 2
Z3  A 1 A 3 A 2 Z3
Z3 A 1 A 3 A 3 A 2 Z3 | a Z 3 A 1 A 3 A 3 A 2
Z3 
All A3Aprod
1 A3 A
n
s 2are in GNF Z3 | a A 1 A 3 A 3 A 2 Z3 | b A 3 A 3 A 2 Z3
A 3  b A 3 A 2 | b A 3 A 2 Z3 | Substitute in Z3  A1 A3 A2
a Z3 | a
Z3  b A 3 A 2 A 1 A 3 A 3 A 2 | b A 3 A 2 Z3
15
A A A A |aZ A A A A |aA