0
Explain with an example Chomsky Normal Form

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2014

0
0
  • A context-free grammar G = (V, Σ, R, S) is said to be in Chomsky Normal Form (CNF), if and only if every rule in R is of one of the following forms:

    1. A → a, for some A ∈ V and some a ∈ Σ
    2. A → BC, for some A ∈ V and B, C ∈ V \ {S}
    3. S →є

    For a Context Free Grammar to be in Chomsky Normal Form(CNF), the grammar should yield productions such as :

    A => BC or

    A => a

    Where a is a terminal and A,B and C are non-terminals

    We consider an example

    S => bA | aB

    A => bAA | aS | a

    B => aBB | bS | b

    For CNF, A => BC (two nonterminals)

    Or

    A => a (one terminal)

    Consider S => bA

    S => BA which is a CNF (substituting B => b)

    Consider S => aB

    S => AB which is CNF(substituting A => a)

    Consider A => aS

    Let $C_1$ => a

    A => $C_1S$ which is CNF

    Consider A =>bAA

    A => BAA (substituting B => b)

    Let $C_2$ => BA

    A => $C_2A$ which is CNF

    Consider B => bS

    Let $C_3$ => b

    B => $C_3S$ which is CNF

    Consider B =>aBB

    B => ABB (Substituting A =>a)

    Let $C_4$ => AB

    B => $C_4B$ which is CNF

0
Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more