Chomsky & Greibach �Normal Forms

Chomsky & Greibach �Normal Forms in toc

2. Presentation Outline
2
•Introduction
•Chomsky normal form
•Preliminary simplifications
•Final steps
•Greibach Normal Form
•Algorithm (Example)
• Summary

3. Introduction
3
Grammar: G = (V, T, P, S))&*(+
T = { a, b }Terminals '&(,(
V = A, B, CVariables#
SStart Symbol•&#-
P = S → AProduction

4. Introduction
4
Grammar example
S → aBSc
S → abc
Ba → aB
Bb → bb/&* •





0 12+
L = { a
n
b
n
c
n
| n ≥ 1 }
S aBSc aBabcc aaBbcc aabbccÞÞÞÞ

5. Introduction
5
Context free grammar
The head of any production contains only one
non-terminal symbol
S → P
P → aPb
P → ε/&* •



0 16+
L = { a
n
b
n
| n ≥ 0 }

6. Presentation Outline
6May 27, 2009
•Introduction
•Chomsky normal form
•Preliminary simplifications
•Final simplification
•Greibach Normal Form
•Algorithm (Example)
• Summary

7. Chomsky Normal Form
7
A → BC
A → α
A context free grammar is said to be in Chomsky
Normal Form if all productions are in the following
form:
• A, B and C are non terminal symbols
• α is a terminal symbol

8. Presentation Outline
8
•Introduction
•Chomsky normal form
•Preliminary simplifications
•Final steps
•Greibach Normal Form
•Algorithm (Example)
• Summary

9. Preliminary Simplifications
9 %#
Eliminate Useless Symbols1 '
Eliminate ε productions 2
Eliminate unit productions3
There are three preliminary simplifications

10. Preliminary Simplifications
10
Eliminate Useless Symbols
We need to determine if the symbol is useful by
identifying if a symbol is generating and is reachable
• X is generating if X ω for some terminal string ω.
• X is reachable if there is a derivation X αXβ
for some α and β
Þ
Þ
*
*

11. Preliminary Simplifications
11May 27, 2009
Example: Removing non-generating symbols#89:
8
S → AB | a
A → b
Initial CFL grammar# 8 9 :
8
S → AB | a
A → b
Identify generating symbols # 8
8
S → a
A → b
Remove non-generating

12. Preliminary Simplifications
12
Example: Removing non-reachable symbols # 8
S → a Eliminate non-reachable # 8
8
S → a
A → b
Identify reachable symbols

13. Preliminary Simplifications
13
The order is important. #89:
8
S → AB | a
A → b
Looking first for non-reachable symbols and then
for non-generating symbols can still leave some
useless symbols. #8
8
S → a
A → b

14. Preliminary Simplifications
14
Finding generating symbols
If there is a production A → α, and every symbol
of α is already known to be generating. Then A is
generating #89:
8
S → AB | a
A → b
We cannot use S → AB
because B has not been
established to be generating

15. Preliminary Simplifications
15
Eliminate Useless Symbols1
Eliminate ε productions 2
Eliminate unit productions3
There are three preliminary simplifications

16. Preliminary Simplifications
16
Eliminate ε Productions
•In a grammar ε productions are convenient but
not essential
•If L has a CFG, then L – {ε} has a CFG
Nullable variable+
A εÞ*

17. Preliminary Simplifications
17
If A is a nullable variable
•Whenever A appears on the body of a production
A might or might not derive ε
S → ASA | aB
A → B | S
B → b | ε
Nullable: {A, B}

18. Preliminary Simplifications
18
•Create two version of the production, one with
the nullable variable and one without it
•Eliminate productions with ε bodies
S → ASA | aB
A → B | S
B → b | ε
S → ASA | aB | AS | SA | S | a
A → B | S
B → b
Eliminate ε Productions

19. Preliminary Simplifications
19
•Create two version of the production, one with
the nullable variable and one without it
•Eliminate productions with ε bodies
S → ASA | aB
A → B | S
B → b | ε
S → ASA | aB | AS | SA | S | a
A → B | S
B → b
Eliminate ε Productions

20. Preliminary Simplifications
20
•Create two version of the production, one with
the nullable variable and one without it
•Eliminate productions with ε bodies
S → ASA | aB
A → B | S
B → b | ε
S → ASA | aB | AS | SA | S | a
A → B | S
B → b
Eliminate ε Productions

21. Preliminary Simplifications
21
Eliminate Useless Symbols1
Eliminate ε productions 2
Eliminate unit productions3
There are three preliminary simplifications

22. Preliminary Simplifications
22
Eliminate unit productions
A unit production is one of the form A → B where both
A and B are variables
A BÞ*
A → B, B → ω, then A → ω
Identify unit pairs

23. Eliminate unit productions
•Consider the CFG
S->0A | 1B|C
A-> 0S|00
B->1|A
C->01
remove unit productions.
S-> C
B-> A unit productions
S->0A|1B|01
A->0S|00
B->1|0S|00
May 27, 2009 23

24. Brain Activity
Can you see both the frog and the horse on this visual illusion?

25. Brain Activity
Is that a polar bear or a seal on the cool optical illusion picture below?

26. Brain Activity
Victory or defeat? Both

27. Brain Activity

28. Brain Activity