Chomsky Normal Form - Converting A Grammar To Chomsky Normal Form

Converting A Grammar To Chomsky Normal Form

  1. Introduce
    Introduce a new start variable, and a new rule where is the previous start variable.
  2. Eliminate all rules
    rules are rules of the form where and where is the CFG's variable alphabet.
    Remove every rule with on its right hand side (RHS). For each rule with in its RHS, add a set of new rules consisting of the different possible combinations of replaced or not replaced with . If a rule has as a singleton on its RHS, add a new rule unless has already been removed through this process. For example, examine the following grammar :
    has one rule. When the is removed, we get the following:
    Notice that we have to account for all possibilities of and so we actually end up adding 3 rules.
  3. Eliminate all unit rules
    After all the rules have been removed, you can begin removing unit rules, or rules whose RHS contains one variable and no terminals (which is inconsistent with CNF).
    To remove
    add rule unless this is a unit rule which has already been removed.
  4. Clean up remaining rules that are not in Chomsky normal form.
    Replace with where are new variables.
    If, replace in above rules with some new variable and add rule .

Read more about this topic:  Chomsky Normal Form

Famous quotes containing the words converting a, converting, grammar, chomsky, normal and/or form:

    “Sigh no more, ladies, sigh no more,
    Men were deceivers ever,
    One foot in sea and one on shore,
    To one thing constant never:
    Then sigh not so, but let them go,
    And be you blithe and bonny,
    Converting all your sounds of woe
    Into Hey nonny, nonny.”
    —William Shakespeare (1564–1616)

    “A way of certifying experience, taking photographs is also a way of refusing it—by limiting experience to a search for the photogenic, by converting experience into an image, a souvenir. Travel becomes a strategy for accumulating photographs.”
    —Susan Sontag (b. 1933)

    “I demand that my books be judged with utmost severity, by knowledgeable people who know the rules of grammar and of logic, and who will seek beneath the footsteps of my commas the lice of my thought in the head of my style.”
    —Louis Aragon (1897–1982)

    “Resistance is feasible even for those who are not heroes by nature, and it is an obligation, I believe, for those who fear the consequences and detest the reality of the attempt to impose American hegemony.”
    —Noam Chomsky (b. 1928)

    “We have been weakened in our resistance to the professional anti-Communists because we know in our hearts that our so-called democracy has excluded millions of citizens from a normal life and the normal American privileges of health, housing and education.”
    —Agnes E. Meyer (1887–1970)

    “The sense of an entailed disadvantage—the deformed foot doubtfully hidden by the shoe, makes a restlessly active spiritual yeast, and easily turns a self-centred, unloving nature into an Ishmaelite. But in the rarer sort, who presently see their own frustrated claim as one among a myriad, the inexorable sorrow takes the form of fellowship and makes the imagination tender.”
    —George Eliot [Mary Ann (or Marian)