Converting Cfgs to Cnf (Chomsky Normal Form) by Richard Cole

1134 Words5 Pages
Converting CFGs to CNF (Chomsky Normal Form) Richard Cole October 17, 2007 A CNF grammar is a CFG with rules restricted as follows. The right hand side of a rule consists of: i. Either a single terminal, e.g. A → a. ii. Or two variables, e.g. A → BC, iii. Or the rule S → , if is in the language. iv. The start symbol S may appear only on the left hand side of rules. Given a CFG G, we show how to convert it to a CNF grammar G generating the same language. We use a grammar G with the following rules as a running example. S → ASA | aB; A → B | S; B → b | We proceed in a series of steps which gradually enforce the above CNF criteria; each step leaves the generated language unchanged. Step 1 For each terminal a, we introduce a new variable, Ua say, add a rule Ua → a, and for each occurrence of a in a string of length 2 or more on the right hand side of a rule, replace a by Ua . Clearly, the generated language is unchanged. Example: If we have the rule A → Ba, this is replaced by Ua → a, A → BUa . This ensures that terminals on the right hand sides of rules obey criteria (i) above. This step changes our example grammar G to have the rules: S → ASA | Ua B; A → B | S; B → b | ; Ua → a 1 2 Step 2 For each rule with 3 or more variables on the righthand side, we replace it with a new collection of rules obeying criteria (ii) above. Suppose there is a rule U → W1 W2 · · · Wk , for some k ≥ 3. Then we create new variables X2 , X3 , · · · , Xk−1 , and replace the prior rule with the rules: U → W1 X2 ; X2 → W2 X3 ; · · · ; Xk−2 → Wk−2 Xk−1 ; Xk−1 → Wk−1 Wk . Clearly, the use of the new rules one after another, which is the only way they can be used, has the same effect as using the old rule U → W1 W2 · · · Wk . Thus the generated language is unchanged. This ensures, for criteria (ii) above, that no right hand side has more than 2 variables. We have yet to eliminate right

More about Converting Cfgs to Cnf (Chomsky Normal Form) by Richard Cole

Open Document