chomsky-normal-form

How do I convert to Chomsky Normal Form(CNF)


How do I convert below grammar to CNF?

S → ASA | aB

A → B | S

B → b | ε

Solution

  • We can split the transformation of context free grammars to Chomsky Normal Form into four steps.

    1. The Bin step ensures that all alternatives in all productions contains no more than two terminals or non-terminals.
    2. The Del step "deletes" all empty string tokens.
    3. The Unit steps "inlines" productions that directly map to a single non-terminal.
    4. The Term step makes sure terminals and non-terminals are not mixed in any alternative.

    From your example, describing each step, the transformation to CNF can look like the following.

    Bin

    Alternatives in production S is split up into smaller productions. New non-terminals are T.

    S → AT | aB
    A → B | S
    B → b | ε
    T → SA
    

    Del

    From the production of S, nullable non-terminals A and B were factored out.

    S → AT | T | aB | a
    A → B | S
    B → b | ε
    T → SA
    

    For the production of A, no action need be taken.

    S → AT | T | aB | a
    A → B | S
    B → b | ε
    T → SA
    

    From the production of B, empty string tokens were removed.

    S → AT | T | aB | a
    A → B | S
    B → b
    T → SA
    

    From the production of T, nullable non-terminal A were factored out.

    S → AT | T | aB | a
    A → B | S
    B → b
    T → SA | S
    

    Unit

    "Inlined" the production for B in A.

    S → AT | T | aB | a
    A → b | S
    B → b
    T → SA | S
    

    Term

    Replaced a terminal "a" in production S with the new non-terminal U.

    S → AT | T | UB | a
    A → b | S
    B → b
    T → SA | S
    U → a
    

    And you're done.