Context-Free Grammars – Chomsky Normal Form Lecture 16 Section 2.1 Wed, Sep 26, 2007 Chomsky Normal Form • A context-free grammar is in Chomsky Normal Form (CNF) if each rule is of the form • A BC, or • A a, where B and C are not S. • Furthermore, the rule S is allowed. Chomsky Normal Form • Theorem: Every context-free language is generated by a grammar in CNF. Chomsky Normal Form • Constructive proof (outline): • • • • Add a new start symbol S0. Eliminate all rules A . Eliminate all unit rules A B. Convert all remaining rules to the proper form. Chomsky Normal Form • Proof (detailed): • Add a new start symbol S0. • Add the rule S0 S. • Eliminate all rules A . • For each rule A and each rule B uAv, add a rule B uv. • Eliminate the rule A . Example • Start with the grammar • S SXS | • X ab | • Add the rule • S0 S Example • We now have • S0 S • S SXS | • X ab | Example • Apply the rules S and X to the other rules, creating the rules • • • • • S S S S S X SS XS SX S • Don’t bother with the last rule. Example • Eliminate the rules •S •X Example • Add the rule • S0 because in the original, S could be replaced by . Example • We now have • S0 S | • S SXS | SS | SX | XS | X • X ab Chomsky Normal Form • Proof (detailed): • Eliminate all unit rules A B. • If A B and B u are rules, then add the rule A u. • Eliminate the rule A B. Chomsky Normal Form • Add the rules • S ab • S0 SXS | SS | SX | XS | X | ab • Eliminate the rules • S0 S •SX Example • We now have • S0 SXS | SS | SX | XS | ab | • S SXS | SS | SX | XS | ab • X ab Chomsky Normal Form • Eliminate all mixed rules. • Add rules •Aa for all terminals appearing in strings of length 2. • Then replace a with A in those strings. Example • Add the rules •Aa •Bb and rewrite the string ab as AB. Example • We now have • • • • • S0 SXS | SS | SX | XS | AB | S SXS | SS | SX | XS | AB X AB Aa Bb Chomsky Normal Form • Finally, eliminate all long rules. • Break all strings of length 2 into a series of strings of length 2. Chomsky Normal Form • Replace the rule • A B1B2…Bk with • • • • • A B1C1 C1 B2C2 … Ck – 2 Bk – 2Ck – 2 Ck – 1 Bk – 1Bk Example • Replace • S0 SXS • S SXS • with • S0 SY • S SY • Y XS Example • The final result is • • • • • • S0 SY | SS | SX | XS | AB | S SY | SS | SX | XS | AB X AB Y XS Aa Bb A Derivation in CNF • Use this grammar in CNF to derive the string ababab. • S0 SY SXS ABXS ABABS ABABAB aBABAB abABAB abaBAB ababAB ababaB ababab. CNF Derivations • Theorem: If a grammar G is in CNF and a string w in L(G) has length n, then w will be derived from G in exactly 2n – 1 steps. The Membership Problem • This theorem allows us to determine whether a given string is derivable from a given grammar. • This is called the Membership Problem. Example • Show that the string abba is not derivable from the grammar of the previous example. A Tree of all Possible Derivations S0 SY SY SS AB XS SS AB SY SS AB ABSS SY a b etc. Example • Put the grammar E E + E | E * E | (E) | a | b | c into CNF. • Then show that the string c++ is not derivable from it.