Formal Languages

Simplifications of CFGs
2
• Why Simplification….?
• By removing the productions of the form
A→ λ
A →B
We can make the process easier

• In this chapter we study several transformations and substitutions that will be

useful in subsequent discussions.

• We also investigate normal forms for context-free grammars.

• A normal form is a grammatical form, so that any Context Free grammar has an
equivalent normal-form version. We introduce two of the most useful of these, the
Chomsky normal form and the Greibach normal form.

3
A Useful Substitution Rule

then

4
Example 1:

5
 Removing Useless Productions

the production S → A clearly plays no role, as A cannot be transformed into a

terminal string. While A can occur in a string derived from S, this can never lead
to a sentence. Removing this production leaves the language unaffected and is a
simplification by any definition.

6
 Exampe 2:

The two reasons why a variable is useless:

→ It cannot be reached from the start symbol
→ It cannot derive a terminal string.

7
Example 3: Eliminating useless productions

→ First, we identify the set of variables that can lead to a

terminal string.
→ A → a and B → aa, the variables A and B belong to this
set. So does S, because S ⇒ A ⇒ a. All leads to terminals.
→ Here C is useless bcos it is not giving a sentence.
S→C C → aCb ( remains in sentential form…)

8
Removing C and its corresponding productions, we are led to the grammar G1 with
variables V1 = {S, A, B}, terminals T = {a}, and productions

→ Next we want to eliminate the variables that cannot be reached from

the start variable. For this,

→ We can draw a dependency graph for the variables.

→ A variable is useful only if there is a path from the

vertex labeled S to the vertex labeled with that variable

9
 Dependency graph for the production

So after removing the useless production we get

10
Removing λ-Productions

11
A grammar may generate a language not containing λ, yet have some λ-
productions or nullable variables. In such cases, the λ-productions can be
removed.

12
Example 4:

→ Find all nullable variables

→ Here we have B → λ, C → λ, A → λ
→ So A, B and C are nullable variables
13
After removing λ productions using substitution
rule the new grammar is given as

14
Removing Unit-Productions

15
Proof: Obviously, any unit-production of the form A → A can be
removed from the grammar without effect, and we need only consider
A → B, where A and B are different variables.

→ The new grammar is generated by first putting into all

non-unit productions of P.

→ Then draw dependency graph only with unit productions.

S→B
B→A
A→B

16
Example 5:

After including non unit productions

we get a new grammar

17
We can remove all undesirable productions using the following
sequence of steps:

18
 Example 6:
Eliminate useless productions from the following
1) 4)
S → aA | bB
S → aA
A → aA | a A → a | aA
B → bB
D → ab | Ea
E → aC | d
Productions Only
with terminals
S → aA (remove B)
2) A→ a S also derives 3) A → aA |a
D → ab terminal thru A D → ab| E not reachable from A
and not thru B E → aC |d
E→d
19
 Example 6:
Eliminate λ productions from the following
1) 3)
S → BAAB S → BAAB | AAB| BAB| BAA|
A → 0A2| 2A0 | λ AB| BB| BA| AA| B | A
B → AB | 1B | λ A → 0A2| 2A0| 02| 20

B → AB| 1B| A| 1

2)
S → BAAB | AAB| BAB| BAA| AB| BB| BA| AA| B | A
A → 0A2| 2A0| 02| 20
B → AB| 1B| A|B| 1 can be removed

20
 Example 7:
Eliminate unit productions from the following
1) 4)
S → AB
S→ AB
A→a
A→ a
B→C|b
B → b | bC | d | Ab
C→D
C → bC | d | Ab
D → E | bC
D → d | Ab| bC
E → d | Ab
E → d | Ab

2)
3)
B→C
C→D
D→E
B C D E

21
 Remove all unit, useless and λ

1) S → aA | aBB 2) S → aA
A → aaA | λ A → BB
B → bC | bbC B → aBb |λ
C→B

22
Two Important Normal Forms

→ Chomsky Normal Form

→ Greibach Normal Form

23
Chomsky Normal Form
• In this CNF , the number of symbols on the right of a
production is strictly limited.
• The string on the right of a production consist of no
more than two symbols

24
Example 1:

25
Any context-free grammar G = (V, T, S, P) with λ ∉ L (G) has an
equivalent grammar in Chomsky normal form.

Proof: Because of Theorem 6.5, we can assume without loss

of generality that G has no λ- productions and no unit-
productions. The construction of will be done in two steps.

26
27
→ This part of the algorithm removes all terminals from productions
whose right side has length greater than one, replacing them with
newly introduced variables.

→ At the end of this step we have a grammar G1 all of whose

productions have the form

28
29
Example 2:
Convert the grammar with productions

to Chomsky normal form.

30
31
 Greibach Normal Form
Another useful grammatical form is the Greibach normal form. Here we put
restrictions not on the length of the right sides of a production, but on the positions in
which terminals and variables can appear.

Definition 6.5
A context-free grammar is said to be in Greibach normal form if all productions
have the form A → ax, where a ∈ T and x ∈ V*

32
Example 3:

33
 Convert the following to CNF

1] S → 0A | 1B 3] S → abAB
A → 0AA | 1S | 1 A → bAB | λ
B → 1BB | 0S | 0 B → Baa|A| λ

2] S → AB | aB
A → aab | λ
B → bbA

34
 Convert the following to GNF

1] S → aSb |bSa | a|b

2] S → aSb | a|b

3] S → ab | aS | aaS

4] S → ABb | a
A → aaA | B
B → bAb
35
Slides downloaded from peter linz
just go thru all the slides

36
 A Substitution Rule

Equivalent
grammar
S → aB
S → aB | ab
A → aaA
Substitute A → aaA
A → abBc B →b A → abBc | abbc
B → aA
B → aA
B→b
37
 A Substitution Rule
S → aB | ab
A → aaA
A → abBc | abbc
B → aA
Substitute
B → aA
S → aB | ab | aaA
Equivalent
A → aaA
A → abBc | abbc | abaAc
grammar
38
In general:
A → xBz

B → y1

Substitute
B → y1

equivalent
A → xBz | xy1z grammar
39
 Nullable Variables

 − production : A→

Nullable Variable: A  

40
 Removing Nullable Variables

Example Grammar:

S → aMb
M → aMb
M →

Nullable variable

41
 Final Grammar

S → aMb
S → aMb
Substitute S → ab
M → aMb M →
M → aMb
M →
M → ab

42
 Unit-Productions

Unit Production: A→ B

(single variables on both sides)

43
 Removing Unit Productions

Observation:

A→ A

Is removed immediately

44
Example Grammar:

S → aA
A→a|B
B → A | bb

45
S → aA S → aA
A→a A → a | bb
Substitute
A→ B B→A
A→ B
B→A B → bb
B → bb

46
S → aA | aB
S → aA
A→a Substitute A → a | bb
B→A B→A
B → a | bb
B → bb

47
 Useless Productions

S → aSb
S →
S→A
A → aA Useless Production

Some derivations never terminate...

S  A  aA  aaA    aaaA  
48
Another grammar:

S→A
A → aA
A→
B → bA Useless Production
Not reachable from S

49
In general: contains only
terminals
if S    xAy    w

w L(G )

then variable A is useful

otherwise, variable A is useless

50
A production A → x is useless
if any of its variables is useless

S → aSb
S → Productions
Variables S→A useless
useless A → aA useless
useless B→C useless

useless C→D useless

51
 Removing Useless Productions

Example Grammar:

S → aS | A | C
A→a
B → aa
C → aCb

52
Remove useless productions

53
 First: find all variables that can produce
strings with only terminals

S → aS | A | C Round 1: { A, B}
A→a S→A
B → aa
C → aCb Round 2: { A, B, S }

54
 Keep only the variables
that produce terminal symbols: { A, B, S }
(other variables are useless)

S → aS | A | C
A→a S → aS | A
B → aa A→a
C → aCb B → aa
Remove useless productions
55
Second: Find all variables
reachable from S

Use a Dependency Graph

S → aS | A
A→a S A B
B → aa not
reachable

56
 Keep only the variables
reachable from S
(the other variables are useless)

Final Grammar
S → aS | A
S → aS | A
A→a
A→a
B → aa

Remove useless productions

57
 Removing All

Step 1: Remove Nullable Variables

Step 2: Remove Unit-Productions

Step 3: Remove Useless Variables

58
 Normal Forms
for
Context-free Grammars

59
 Chomsky Normal Form

Each production has form:

A → BC or A→a

variable variable terminal

60
Examples:

S → AS S → AS
S →a S → AAS
A → SA A → SA
A→b A → aa
Chomsky Not Chomsky
Normal Form Normal Form

61
 Conversion to Chomsky Normal Form

Example: S → ABa
A → aab
B → Ac

Not Chomsky
Normal Form

62
Introduce variables for terminals: Ta , Tb , Tc

S → ABTa
S → ABa A → TaTaTb
A → aab B → ATc
B → Ac Ta → a
Tb → b
Tc → c
63
Introduce intermediate variable: V1

S → AV1
S → ABTa
V1 → BTa
A → TaTaTb
A → TaTaTb
B → ATc
B → ATc
Ta → a
Ta → a
Tb → b
Tb → b
Tc → c
Tc → c
64
Introduce intermediate variable: V2
S → AV1
S → AV1
V1 → BTa
V1 → BTa
A → TaV2
A → TaTaTb
V2 → TaTb
B → ATc
B → ATc
Ta → a
Ta → a
Tb → b
Tb → b
Tc → c
Tc → c 65
 Final grammar in Chomsky Normal Form:
S → AV1
V1 → BTa
A → TaV2
Initial grammar
V2 → TaTb
S → ABa B → ATc
A → aab Ta → a
B → Ac Tb → b
Tc → c 66
In general:

From any context-free grammar

(which doesn’t produce  )
not in Chomsky Normal Form

we can obtain:
An equivalent grammar
in Chomsky Normal Form

67
 The Procedure

First remove:

Nullable variables

Unit productions

68
Then, for every symbol a:

Add production Ta → a

In productions: replace a with Ta

New variable: Ta
69
Replace any production A → C1C2 Cn

with A → C1V1
V1 → C2V2

Vn−2 → Cn−1Cn

New intermediate variables: V1, V2 , ,Vn−2

70
Theorem: For any context-free grammar
(which doesn’t produce  )
there is an equivalent grammar
in Chomsky Normal Form

71
 Observations

• Chomsky normal forms are good

for parsing and proving theorems

• It is very easy to find the Chomsky normal

form for any context-free grammar

72
 Greibach Normal Form

All productions have form:

A → a V1V2 Vk k 0

terminal variables

73
Examples:

S → cAB
S → abSb
A → aA | bB | b
S → aa
B→b

Greibach Not Greibach

Normal Form Normal Form

74
Conversion to Greibach Normal Form:

S → aTb STb
S → abSb S → aTa
S → aa Ta → a
Tb → b
Greibach
Normal Form
75
Theorem: For any context-free grammar
(which doesn’t produce  )
there is an equivalent grammar
in Greibach Normal Form

76