Question: Algorithm for CFG to CNF conversion
0

Mumbai University > Informatica Technology > Sem 4 > Automata Theory

Marks: 10

Year:May 18

automata theory • 288 views
ADD COMMENTlink
modified 12 weeks ago by gravatar for RB RB ♦♦ 100 written 6 months ago by gravatar for pratikj2208 pratikj22080
0

Algorithm for CFG to CNF conversion

Some important things to note are -

  • For a given grammar there can be more than one CNF.

  • CNF produces the same language as generated by CFG.

  • CNF is used to proproccess the many algorithms for CFG like CYK, etc.

Step 1. Eliminate start symbol from RHS. create new production for the same if required.

So $\rightarrow$ S. where so is new start symbol.

Step 2. Eliminate null, unit and useless productions.

Step 3. Eliminate terminals from RHS if they exist with other terminals or non-terminal.

eg. X $\rightarrow$ XY can be expressed as

X $\rightarrow$ ZY

Z $\rightarrow$ X

Step 4. Eliminate RHS with more than two non-terminals.

eg. X $\rightarrow$ XYZ can be expressed as

X $\rightarrow$ PZ

P $\rightarrow$ XY

ADD COMMENTlink
modified 11 weeks ago by gravatar for Ankit Pandey Ankit Pandey70 written 12 weeks ago by gravatar for RB RB ♦♦ 100
Please log in to add an answer.