Scribd
Upload
17 views5 pages

Chomsky Normal Forms Examples

The document outlines the process of converting a given context-free grammar (CFG) into Chomsky Normal Form (CNF) by eliminating ε-productions, unit productions, and useless symbols. It details the steps taken to simplify the grammar, including the introduction of new variables for terminals and breaking down productions to ensure compliance with CNF rules. The final CNF format for the grammars is presented, demonstrating the transformations made throughout the process.

Uploaded by

latha2009
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
17 views5 pages

Chomsky Normal Forms Examples

The document outlines the process of converting a given context-free grammar (CFG) into Chomsky Normal Form (CNF) by eliminating ε-productions, unit productions, and useless symbols. It details the steps taken to simplify the grammar, including the introduction of new variables for terminals and breaking down productions to ensure compliance with CNF rules. The final CNF format for the grammars is presented, demonstrating the transformations made throughout the process.

Uploaded by

latha2009
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

CHOMSKY NORMAL FORMS

Given the grammar:

S → ABC | BaB
A → aA | BaC | aaa
B → bBb | a | D
C → CA | AC
D→ε

1: Eliminate ε–productions

Nullable variables

• D → ε ⇒ D is nullable

• B → D ⇒ B is nullable

• C → CA | AC (no terminal base case) ⇒ C never derives terminals ⇒ C is useless (we'll


remove later)

So nullable variables: D, B

Now remove ε-productions.

Since B is nullable, we modify productions containing B.

Modify productions containing B:

1. S → ABC

o Remove B ⇒ S → AC

2. S → BaB

o Remove first B ⇒ aB

o Remove last B ⇒ Ba

o Remove both ⇒ a

3. A → BaC

o Remove B ⇒ aC

4. B → bBb

o Remove middle B ⇒ bb

Remove:

D→ε
B→D

Grammar becomes:

S → ABC | AC | BaB | aB | Ba | a
A → aA | BaC | aC | aaa
B → bBb | bb | a
C → CA | AC

Eliminate Unit Productions

There are no direct unit productions like A → B left.

Eliminate Useless Symbols

Check generating symbols

C → CA | AC
C has no terminal-only derivation ⇒ C is non-generating

So remove C and all productions containing C.

Remove:

• S → ABC

• S → AC

• A → BaC

• A → aC

• C → CA

• C → AC

Now grammar becomes:

S → BaB | aB | Ba | a
A → aA | aaa
B → bBb | bb | a

Check reachability:

S → uses B
A is never reachable from S ⇒ remove A

Final useful grammar:

S → BaB | aB | Ba | a
B → bBb | bb | a

Convert to CNF

CNF rules:

• A → BC

• A→a

No mixed terminals + variables


No RHS length > 2
Replace terminals in long productions

Introduce new variables:

X→a
Y→b

Replace terminals:

B→YBY

Length 3 ⇒ break:

Let M → B Y

So:

B→YM
M→BY

Convert B → bb

B→YY

Convert S → BaB

Replace a with X:

S→BXB

Length 3 ⇒ break:

Let N → X B

So:

S→BN
N→XB

Convert S → aB

S→XB

S → a is allowed (A → a form)

Final CNF FORMAT:

S→BN|XB|BX|a
B→YM|YY|a
M→BY
N→XB
X→a
Y→b
EXAMPLE2: Converting CFG to CNF
Convert the given CFG to CNF:

G= { S → ASA | aB,

A → B|S,

B → b|Ɛ

Step 1: if we observe the production rules, we can find that in the first two rules starting state S
appears right-hand side of the productions. We need to add a new starting state S’ and a new
production rule S’ → S.

Step 2: removing null production rules B →Ɛ and A →Ɛ.

After removing B →Ɛ, grammar G

S’ → S,

S → ASA | aB | a ,

A → B | S | Ɛ,

B→b

After removing A →Ɛ, grammar G

S’ → S,

S → ASA | aB | a | AS | SA ,

A→B|S,

B→b

Removing unit production rules, S’ → S, A → B, and A →S

After removing S’ → S, grammar G

S’ → ASA | aB | a | AS | SA,

S → ASA | aB | a | AS | SA ,

A→B|S,

B→b
After removing A → B, grammar G

S’ → ASA | aB | a | AS | SA,

S → ASA | aB | a | AS | SA ,

A→b|S,

B→b

After removing A → S, grammar G

S’ → ASA | aB | a | AS | SA,

S → ASA | aB | a | AS | SA ,

A → b | ASA | aB | a | AS | SA ,

B→b

Step 3: we find some production rules that have more than two symbols on the RHS.

S’ → ASA, S → ASA, A → ASA .

Let’s replace SA by X i.e, X → SA

S’ → AX | aB | a | AS | SA,

S → AX | aB | a | AS | SA ,

A → b | AX | aB | a | AS | SA ,

B → b,

X → SA

Now we will replace terminal symbol a by Y from these rules, S’ → aB, S → aB and A → aB.

Now the grammar G in CNF

S’ → AX | YB | a | AS | SA,

S → AX | YB | a | AS | SA ,

A → b | AX | YB | a | AS | SA ,

B → b,

X → SA,

Y→a

You might also like