Simplifies and normal forms - Theory of Computation

This is one of the topic from Theory of computation.

1. Simplifies form and Normal form

2. Simplifies form

3. Context Free Grammar (CFG)
•A context free grammar is a 4-tuple G=(V, ,S,P)
Ʃ
where
V & are disjoint finite set
Ʃ
S is an element of V and
P is a finite set formulas of the form A → α
V → Non terminal or variable

Ʃ
→ terminal symbols
S → start symbol
P → production rule or grammar rules

4. Context Free Grammar (CFG)
Application
•CFG are extensively used to specify the syntax of programming
language.
•CFG is used to develop parser
Definition: Context Free Language
•Language generated by CFG is called context free language
•Let G= (V, , S, P) be a CFG. The Language generated by G is
Ʃ
L(G):{x */S G* x}
∈Ʃ⟹
•A language L is a context free Language(CFL) if there is a CFG G
so that L=L(G)

5. Simplified form & Normal forms
•In this section we discuss some slight more straight
forward ways of improving a grammer without
changing the resulting language.
1)eliminating certain types of productions that may
be awkward to work to work.
2)standardizing the productions so that they all have
a certaion normal form.

6. Simplifies form
•In this simplifies form there is three type
1) Eliminating Null able Variable(Empty Production Removal)
2) Eliminating Unit Production(Unit production removal)
3) Eliminating Useless Productions(Removing Useless)

7. Eliminating Null able Variable
(Empty Production Removal)
•The productions of context-free grammars can be coerced
into a variety of forms without affecting the expressive power
of the grammars.
•If the empty string does not belong to a language, then there
is a way to eliminate the productions of the form A → ^ from
the grammar.
•If the empty string belongs to a language, then we can
eliminate ^ from all productions save for the single
production S → ^ . In this case we can also eliminate any
occurrences of S from the right-hand side of productions

8. Eliminating Null able Variable
(Empty Production Removal)
•a nullable variable in a CFG G=(V, ,S,P) is defined as follows
Ʃ
1) Any variable A for which P contains A → is nullable
˄
2) if P contain production A → B1B2…..Bn
where B1B2…Bn are nullable variable, then A is nullable.
3) No other variable in V are nullable.
•Example:
S → aX/Yb
X → S/
˄
Y → bY/b
Ans:
S → aX/Yb/a
X → S
Y → bY/b

9. Eliminating Unit Production
(Unit production removal)

10. Eliminating Unit Production
(Unit production removal)

11. Eliminating Unit Production
(Unit production removal)
•Example:
S → Aa/B
A → a/bc/B
B → A/bB
Ans:
Unit production are S → B, A → B and B → A
S → Aa/A/bbS → Aa/a/bc/bb
A → a/bc/B A → a/bc/A/bb
A → a/bc/bbB → A/bb
B → A/bb B → a/bc/bb
So CFG after removing unit production is
S → Aa/a/bc/bb
A → a/bc/bb
B → a/bc/bb

12. Normal forms

13. definition

14. Theorem

15. Example of CFG Conversion

16. Removing Rules

17. Removing unit rule

18. More unit rules

19. Converting remaining rules

20. Presentation Outline
20May 27, 2009
•Greibach Normal Form

21. Greibach Normal Form
21May 27, 2009
A → αX
A context free grammar is said to be in
Greibach Normal Form if all productions
are in the following form:
• A is a non terminal symbols
• α is a terminal symbol
• X is a sequence of non terminal symbols.
It may be empty.

22. Step1:
If the start symbol S occurs on some right side, create a
new start symbol S’ and a new production S’ → S.
Step 2:
Remove Null productions. (Using the Null production
removal algorithm discussed earlier)
Step 3:
Remove unit productions. (Using the Unit production
removal algorithm discussed earlier)
Step 4:
Remove all direct and indirect left-recursion.
Step 5:
Do proper substitutions of productions to convert it into
the proper form of GNF.
Algorithm to Convert a CFG into Greibach Normal Form
Greibach Normal Form

23. Greibach Normal Form
23May 27, 2009
Example:
S → XA | BB
B → b | SB
X → b
A → a
S = A
1
X = A
2
A = A
3
B = A
4
A
1
→ A
2
A
3
| A
4
A
4
A
4
→ b | A
1
A
4
A
2
→ b
A
3
→ a
CNF New Labels
Updated CNF

24. Greibach Normal Form
24May 27, 2009
Example:
A
1
→ A
2
A
3
| A
4
A
4
A
4
→ b | A
1
A
4
A
2
→ b
A
3
→ a
First Step
X
k
is a string of zero
or more variablesooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooo
oooo y
s
oPoy
=
R
;
oooo=o>oso


A
i
→ A
j
X
k
j > i
A
4
→ A
1
A
4

25. Greibach Normal Form
25May 27, 2009
Example:
A
1
→ A
2
A
3
| A
4
A
4
A
4
→ b | A
1
A
4
A
2
→ b
A
3
→ a
A
4
→ A
1
A
4
A
4
→ A
2
A
3
A
4
| A
4
A
4
A
4
| b
A
4
→ bA
3
A
4
| A
4
A
4
A
4
| b
First Step
b
p
y b
$
%
&
$ ' p
A
i
→ A
j
X
k
j > i

26. Greibach Normal Form
26May 27, 2009
Example:
Second Step




NnpCp)f"m

+m," -me.ivpr)v





Eliminate

Left Recursions
A
1
→ A
2
A
3
| A
4
A
4
A
4
→ bA
3
A
4
| A
4
A
4
A
4
| b
A
2
→ b
A
3
→ a
A
4
→ A
4
A
4
A
4

27. Greibach Normal Form
27May 27, 209
Example:
Second Step

NnpCp)f"m
+m,"
-me.ivpr)v


Eliminate
Left
Recursions
A
1
→ A
2
A
3
| A
4
A
4
A
4
→ bA
3
A
4
| A
4
A
4
A
4
| b
A
2
→ b
A
3
→ a
A
4
→ bA
3
A
4
| b | bA
3
A
4
Z

| bZ
Z → A
4
A
4
| A
4
A
4
Z

28. Greibach Normal Form
28May 27, 2009
Example:
A
1
→ A
2
A
3
| A
4
A
4
A
4
→ bA
3
A
4
| b | bA
3
A
4
Z | bZ
Z → A
4
A
4
| A
4
A
4
Z
A
2
→ b
A
3
→ ab y 1%
A → αX
GNF

29. Greibach Normal Form
29May 27, 2009
Example:
A
1
→ A
2
A
3
| A
4
A
4
A
4
→ bA
3
A
4
| b | bA
3
A
4
Z | bZ
Z → A
4
A
4
| A
4
A
4
Z
A
2
→ b
A
3
→ a

Z → bA
3
A
4
A
4
| bA
4
| bA
3
A
4
ZA
4
| bZA
4
| bA
3
A
4
A
4
| bA
4
| bA
3
A
4
ZA
4
| bZA
4

A
1
→ bA
3
| bA
3
A
4
A
4
| bA
4
| bA
3
A
4
ZA
4
| bZA
4

30. Greibach Normal Form
30May 27, 2009
Example:
A
1
→ bA
3
|

bA
3
A
4
A
4
| bA
4
| bA
3
A
4
ZA
4
| bZA
4
A
4
→ bA
3
A
4
| b | bA
3
A
4
Z | bZ
Z → bA
3
A
4
A
4
| bA
4
| bA
3
A
4
ZA
4
| bZA
4
| bA
3
A
4
A
4
| bA
4
| bA
3
A
4
ZA
4
| bZA
4

A
2
→ b
A
3
→ a

Grammar in Greibach Normal Form

31. Thank You
14/11/16