انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

Chomsky NORMAL FORM

Chomsky Normal Form

Chomsky Normal Form 

Chomsky Normal Form (CNF) has only productions of the form:

A ? B C or 

A ? a

with A, B, C IV and aIT.

This means all rules are consisting of either a single terminal on the PRODUCTIONS, or they are binary, consisting of two variables.

Here is the algorithm  to convert a given CFG into CNF.

0. Make the initial grammar G free of ?-productions, unit-productions, and useless variables and productions. 

You have rules now, which contain one terminal on the PRODUCTIONS or at least two symbols from V E T on the PRODUCTIONS.

1. We substitute terminals a_i, which appear in complex PRODUCTIONS (with more than one symbol), with new variables C₁, C₂,... 

Add these C₁, C₂,... to V to form V .  

We have to add matching new productions:   C_i ? a_i   to P to form P .

Productions in P have either a single terminal on the PRODUCTIONS, or at least 2 variables:

 A ? a   or  A ? V₁ ... V_n  with  V_i I V    for i=1,...,n   and  n?2

2. We split up the non-terminal productions in P and make them "binary".

We introduce new variables D₁, D₂, ... which we add to V .

Every  A ? V₁ ... V_n   in P is now substituted with a set of new productions:

   A ? V₁ D₁ 

  D₁ ? V₂ D₂ 

  D₂ ? V₃ D₃

         _{. . .}

  D_n-1 ? V_n-1 V_n 

The grammar is now in Chomsky NF: 

EXAMPLE 1: TRANSFORM A CFG INTO Chomsky NORMAL FORM  

 the grammar G with V={S, A, B}, T={a, b} and productions P 

S ? A

A ? a B a | a 

B ? b A b | b |D

 S ? a B a | a 

B ? b A b | b

S ? C1 B C1 | a

B ? C2 A C2| b

C1?a

C2?b

S ? C1 D1 | a

B ? C2 D2 | b

D1?  B C1

D2 ? A C2

C1? a

C2? b

 H.W   TRANSFORM A CFG INTO Chomsky NORMAL FORM

S ?Y X Z \ Y

 Y   ?0Y1\01

 X ?aXb\l

 Z   ?bZ

DONE

Instructor:  Mohamed U. Mahdi