Chomsky

SIMPLIFICATION OF CONTEXT FREE DIAGRAMS Presentation On “CHOMSKY NORMAL FORM” BY GAURAV NIGAM IInd B.Tech

COMPUTER SCIENCE & ENGG. DEPARTMENT H.B.T.I. KANPUR

AGENDA Simplification of CFG Removing useless Productions Removing λ- Productions Removing unit- Productions Normal Forms : Chomsky Normal Form Example

In general:

A → xBz B → y1 Substitute

B → y1

A → xBz | xy1z

equivalent grammar

A Substitution Rule S → aB A → aaA A → abBc B → aA B→b

Substitute

B→b

Equivalent grammar

S → aB | ab A → aaA A → abBc | abbc B → aA

A Substitution Rule

S → aB | ab A → aaA A → abBc | abbc B → aA

Substitute

B → aA

S → aB | ab | aaA A → aaA A → abBc | abbc | abaAc

Equivalent grammar

Substitution Rule Let G = (V,T,S,P) be a context-free grammar. & p be the production of form A→ x1 B x2 Assume that A and B are different variable and that B → y1|y2|…|yn A→ x1y1x2|x1y2x2|….x1ynx2

Example

A→a | aaA | abBc B→ abbA | b

Substitute B

A→ a | aaA | ababbAc | abbc B→ abbA | b

Simplification of CFG

Removing use less Production Let G = (V,T,S,P) be a CFG. A variable AεV is said to be useful iff there is at least one w ε L(G) such that S→* xAy→ * w, with x,y,in(V џ T)*

Useless Productions S → aSb S →λ S→A A → aA

Useless Production

Some derivations never terminate...

S ⇒ A ⇒ aA ⇒ aaA ⇒  ⇒ aa  aA ⇒ 

Another grammar:

S→A A → aA A→λ B → bA

Useless Production

Not reachable from S

contains only terminals

In general: if

S ⇒  ⇒ xAy ⇒  ⇒ w

w∈ L(G ) then variable

A

is useful

otherwise, variable

A

is useless

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

Variables useless useless useless

S → aSb S →λ S→A A → aA B→C C→D

Productions useless useless useless useless

Removing Useless Productions Example Grammar:

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

First:

find all variables that can produce strings with only terminals

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

Round 1:

{ A, B} S→A

Round 2:

{ A, B, S }

Keep only the variables that produce terminal symbols:

{ A, B, S }

(the rest variables are useless)

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

S → aS | A A→a B → aa

Remove useless productions

Second: Find all variables reachable from

S

Use a Dependency Graph

S → aS | A A→a B → aa

S

A

B not reachable

Keep only the variables reachable from S (the rest variables are useless)

S → aS | A A→a B → aa

Final Grammar

S → aS | A A→a

Remove useless productions

Removing λ -Production Any production of a CFG of the form A→ λ is called a λ- production. Any variable for which the derivation A→ * λ is possible is called Null able .

Example S→ ABAC A→ Aa | λ B→ bB | λ C→ c

Example • • • •

S→ ABAC A→ Aa | λ B→ bB | λ C→ c

S→ ABC | BAC | BC A→ a

Right side that Contains A

Occurrence of A S→ ABAC A→ Aa

Cont… • • • •

S→ ABAC A→ Aa | λ B→ bB | λ C→ c

• S→ABAC | ABC | BAC | BC • A→ Aa | a • B→ bB | λ • C →c

Cont… • S→ABAC | ABC | BAC | BC • A→ Aa | a • B→ bB | λ • C →c

S→ABAC | ABC | BAC | BC | AAC | AC | C A →Aa | a B →bB | b C →c Final grammar

Removing unit production Any production of a context- free grammar of the form A→ B, where A,B ε V is called Unit-Production

Example Grammar:

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

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

Substitute

A→ B

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

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

Remove

B→B

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

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

Substitute

B→A

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

Remove repeated productions

Final grammar

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

S → aA | aB A→a B → bb

Chomsky Normal Form

Chomsky Normal Form Each productions has form:

A → BC variable

or variable

A→a terminal

Convertion to Chomsky Normal Form • Example:

S → ABa A → aab B → Ac

Not Chomsky Normal Form

Introduce variables for terminals:

Ta , Tb , Tc

S → ABTa S → ABa A → aab B → Ac

A → TaTaTb B → ATc Ta → a Tb → b Tc → c

Introduce intermediate variable:

S → ABTa A → TaTaTb B → ATc Ta → a Tb → b Tc → c

V1

S → AV1 V1 → BTa A → TaTaTb B → ATc Ta → a Tb → b Tc → c

Introduce intermediate variable:

S → AV1 V1 → BTa A → TaTaTb B → ATc Ta → a Tb → b Tc → c

V2

S → AV1 V1 → BTa A → TaV2 V2 → TaTb B → ATc Ta → a Tb → b Tc → c

Final grammar in Chomsky Normal Form:

S → AV1 V1 → BTa Initial grammar

S → ABa A → aab B → Ac

A → TaV2 V2 → TaTb B → ATc Ta → a Tb → b Tc → c

Another example • S → ASA | aB • A→B|S • B→ b|λ • I will convert this to Chomsky Normal Form………….

Eliminating the rule B → λ • • • •

So → S S → ASA | aB A→ B|S B→ b|λ

• • • •

So → S S → ASA | aB | a A→ B|S|λ B→ b

Eliminating the rule A → λ • • • •

So → S S → ASA | aB | a A→ B|S|λ B→ b

• So → S • S → ASA | AS | SA | S | aB | a • A→ B|S • B→ b

Eliminating the rule S → S • So → S • S → ASA | AS | SA | S | aB | a • A→ B|S • B→ b

• So → S • S → ASA | AS | SA | aB | a • A→ B|S • B→ b

Eliminating the rule So→ S • So → S • S → ASA | AS | SA | aB | a • A→ B|S • B→ b

• So → ASA | AS | SA | aB | a • S → ASA | AS | SA | aB | a • A→ B|S • B→ b

Eliminating the rule A→ B • S0 → ASA | AS | SA | aB | a • S → ASA | AS | SA | aB | a • A→ B|S • B→ b

• S0 → ASA | AS | SA | aB | a • S → ASA | AS | SA | aB | a • A→ S|b • B→ b

Eliminating the rule A→ S • S0 → ASA | AS | SA | aB | a • S → ASA | AS | SA | aB | a • A→ S|b • B→ b

• S0 → ASA | AS | SA | aB | a • S → ASA | AS | SA | aB | a • A → ASA | AS | SA | aB | a | b • B→ b

Spliting the rule S→ ASA • S0 → ASA | AS | SA | aB | a • S → ASA | AS | SA | aB | a • A → ASA | AS | SA | aB | a | b • B→ b

• S0 → AA1 | AS | SA | aB | a • S → AA1 | AS | SA | aB | a • A → AA1 | AS | SA | aB | a | b • A1 → SA • B→ b

Final Grammar • • • • • •

S0 → AA1 | AS | SA | UB | a S → AA1 | AS | SA | UB | a A → AA1 | AS | SA | UB | a | b A1→ SA B→ b U→a

Question ??? • Questions and Comments are welcome… •

• •

? THANKS Have a great Day !