Scribd
Upload
2 views

Simplifies Form and Normal Form

Uploaded by

Iron Man
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views

Simplifies Form and Normal Form

Uploaded by

Iron Man
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 31

Simplifies form and Normal form

Simplifies form
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
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)
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.
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)
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
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
Eliminating Unit Production
(Unit production removal)
Eliminating Unit Production
(Unit production removal)
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/bb S → Aa/a/bc/bb
A → a/bc/B A → a/bc/A/bb
A → a/bc/bb B → 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
Normal forms
definition
Theorem
Example of CFG Conversion
Removing Rules
Removing unit rule
More unit rules
Converting remaining rules
Presentation Outline

• Greibach Normal Form

May 27, 2009 20


Greibach Normal Form

A context free grammar is said to be in


Greibach Normal Form if all productions
are in the following form:

A → αX

• A is a non terminal symbols


• α is a terminal symbol
• X is a sequence of non terminal symbols.
It may be empty.

May 27, 2009 21


Greibach Normal Form
Algorithm to Convert a CFG into Greibach Normal Form
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.
Greibach Normal Form

Example:

S → XA | BB S = A1 A1 → A2A3 | A4A4
B → b | SB X = A2 A4 → b | A1A4
X→b A = A3 A2 → b
A→a B = A4 A3 → a

CNF New Labels Updated CNF

May 27, 2009 23


Greibach Normal Form

Example:

A 1 → A 2A 3 | A 4A 4 First Step
A 4 → b | A 1A 4 AAii →
→ AAjjXXkk jj >> ii
A2 → b Xk is a string of zero
A3 → a
or more variables

A 4 → A 1A 4

May 27, 2009 24


Greibach Normal Form

Example:

First Step
AAii →
→ AAjjXXkk jj >> ii

A 4 → A 1A 4 A 1 → A 2A 3 | A 4A 4
A4 → A2A3A4 | A4A4A4 | b A 4 → b | A 1A 4
A4 → bA3A4 | A4A4A4 | b A2 → b
A3 → a

May 27, 2009 25


Greibach Normal Form

Example:

A1 → A2A3 | A4A4 Second Step


A4 → bA3A4 | A4A4A4 | b
A2 → b
A3 → a Eliminate
Eliminate

Left
Left Recursions
Recursions
A4 → A4A4A4

May 27, 2009 26


Greibach Normal Form

Example:
Second Step

Eliminate
Eliminate
Left
Left
Recursions
Recursions

A4 → bA3A4 | b | bA3A4Z | bZ A1 → A2A3 | A4A4


A4 → bA3A4 | A4A4A4 | b
Z → A4A4 | A4A4Z A2 → b
A3 → a

May 27, 209 27


Greibach Normal Form

Example:

A1 → A2A3 | A4A4
A4 → bA3A4 | b | bA3A4Z | bZ AA →
→ αX
αX
Z → A 4A 4 | A 4A 4 Z
A2 → b GNF
A3 → a

May 27, 2009 28


Greibach Normal Form

Example:
A1 → A2A3 | A4A4
A4 → bA3A4 | b | bA3A4Z | bZ
Z → A4A4 | A4A4 Z
A2 → b
A3 → a

A1 → bA3 | bA3A4A4 | bA4 | bA3A4ZA4 | bZA4

Z → bA3A4A4 | bA4 | bA3A4ZA4 | bZA4 | bA3A4A4 | bA4 | bA3A4ZA4 | bZA4

May 27, 2009 29


Greibach Normal Form

Example:

A1 → bA3 | bA3A4A4 | bA4 | bA3A4ZA4 | bZA4


A4 → bA3A4 | b | bA3A4Z | bZ
Z → bA3A4A4 | bA4 | bA3A4ZA4 | bZA4 | bA3A4A4 | bA4 | bA3A4ZA4 | bZA4
A2 → b
A3 → a

Grammar in Greibach Normal Form

May 27, 2009 30


You
Th ank

14/11/16

You might also like