Chomsky normal form

The Chomsky normal form (abbr .: CNF ) is a normal form for context-free grammars in theoretical computer science . It is named after the linguist Noam Chomsky and is used in the CYK algorithm . A context-free grammar in Chomsky normal form has a simple structure of the production rules and also fulfills the properties of context-sensitive grammars .

Every context-free language has a grammar in Chomsky normal form. Therefore, a Chomsky normal form can be constructed from any context-free grammar that produces the same language. The grammar is then also called a Chomsky normal form of context-free grammar . ${\displaystyle G}$ ${\displaystyle G_{CNF}}$ ${\displaystyle G_{CNF}}$ ${\displaystyle G}$

Another normal form for context-free grammars is the Greibach normal form . An extension of the Chomsky normal form of context-sensitive grammars , the Kuroda normal form . The Chomsky normal form is easy due to the same shortcut with the conjunctiva Normal Form (Engl. Conjunctive normal form) confused.

definition

A formal grammar is in Chomsky normal form when each production from has one of the following forms: ${\displaystyle G=(V,\Sigma ,P,S)}$ ${\displaystyle P}$

• ${\displaystyle A\rightarrow BC}$
• ${\displaystyle A\rightarrow a}$
• ${\displaystyle S\rightarrow \varepsilon }$

wherein , and non-terminal symbols of are and a terminal symbol of is. is the start symbol and the empty word . If the production is part of the grammar, then it can not be on the right side of a production. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle V}$ ${\displaystyle a}$ ${\displaystyle \Sigma }$ ${\displaystyle S}$ ${\displaystyle \varepsilon }$ ${\displaystyle S\rightarrow \varepsilon }$ ${\displaystyle S}$

If you allow any number of non-terminal symbols instead of two on the right-hand side during the first production, then one speaks of a weak Chomsky normal form .

Construction of a Chomsky normal form

If a context-free grammar is available, a grammar in Chomsky normal form can be generated step by step , which generates the same language: ${\displaystyle G=(V,\Sigma ,P,S)}$ ${\displaystyle G'}$

except treat ${\displaystyle S\rightarrow \varepsilon }$

If the grammar contains the rule , a new start symbol for is introduced. The new grammar then receives the rules and . This ensures that the grammar still allows the empty word and the original start symbol can still be used on the right. ${\displaystyle G}$ ${\displaystyle S\rightarrow \varepsilon }$ ${\displaystyle S'}$ ${\displaystyle G'}$ ${\displaystyle S'\rightarrow \varepsilon }$ ${\displaystyle S'\rightarrow S}$

Generate a weak Chomsky normal form

A non-terminal symbol is assigned to each terminal symbol . On the right side of each production, all terminal symbols are replaced by the corresponding non-terminal symbol . Finally, all productions are added to the grammar. ${\displaystyle a}$ ${\displaystyle X_{a}}$ ${\displaystyle a}$ ${\displaystyle X_{a}}$ ${\displaystyle X_{a}\rightarrow a}$

Replace right sides with more than two non-terminals

If there are more than two non-terminals on the right side of a production, two adjacent non-terminals are replaced by a new non-terminal . The production is added to the grammar. This is repeated until there is no more production with more than two non-terminals. ${\displaystyle AB}$ ${\displaystyle Y_{AB}}$ ${\displaystyle Y_{AB}\rightarrow AB}$

${\displaystyle \varepsilon }$- Remove productions

Cross out the rules , except (if any). ${\displaystyle A\rightarrow \varepsilon }$ ${\displaystyle S'\rightarrow \varepsilon }$

If there was previously exactly one production on the left-hand side, delete that everywhere on the right-hand side of the productions, because it cannot be derived to a terminal. ${\displaystyle A}$ ${\displaystyle A}$

If there were previously several productions on the left, add a rule for each rule that contains one on the right in which it was deleted, because the case in which it is derived as an empty word must be considered was or maybe not. The rule is then supplemented with the rule , for example . ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle C\rightarrow AB}$ ${\displaystyle C\rightarrow B}$

From therefore is: ${\displaystyle C\rightarrow AB}$

${\displaystyle C\rightarrow B}$

${\displaystyle C\rightarrow AB}$

Remove chain rules (productions of form A → B)

If you have a chain rule, i. H. a production of the form , removed, a new production is added for each existing production of the form , if this does not result in a chain rule that has already been removed. is any word here; However, the previous changes ensure that there is either exactly one terminal symbol or a word made up of exactly two non-terminal symbols. ${\displaystyle A\rightarrow B}$ ${\displaystyle B\rightarrow w}$ ${\displaystyle A\rightarrow w}$ ${\displaystyle w}$ ${\displaystyle w}$

example

It applies, the grammar above the alphabet with the rules ${\displaystyle \Sigma =\{a,b\}}$

• ${\displaystyle S\rightarrow ASA|aB}$
• ${\displaystyle A\rightarrow B|S}$
• ${\displaystyle B\rightarrow b|\varepsilon }$

to bring into Chomsky normal form.  

1. Add a new start variable

• ${\displaystyle S_{0}\rightarrow S}$
• ${\displaystyle S\rightarrow ASA|aB}$
• ${\displaystyle A\rightarrow B|S}$
• ${\displaystyle B\rightarrow b|\varepsilon }$

  2. Remove transitions ${\displaystyle \varepsilon }$

• ${\displaystyle S_{0}\rightarrow S}$
• ${\displaystyle S\rightarrow ASA|aB|a}$
• ${\displaystyle A\rightarrow B|\varepsilon |S}$
• ${\displaystyle B\rightarrow b}$

  A new rule has been created, which in turn must be treated in the same way: ${\displaystyle \varepsilon }$

• ${\displaystyle S_{0}\rightarrow S}$
• ${\displaystyle S\rightarrow ASA|AS|SA|aB|a}$
• ${\displaystyle A\rightarrow B|S}$
• ${\displaystyle B\rightarrow b}$

  3. Remove all unity rules. These are and . ${\displaystyle A\rightarrow B,A\rightarrow S}$ ${\displaystyle S_{0}\rightarrow S}$

• ${\displaystyle S_{0}\rightarrow S}$
• ${\displaystyle S\rightarrow ASA|AS|SA|aB|a}$
• ${\displaystyle A\rightarrow S}$
• ${\displaystyle B\rightarrow b}$
• ${\displaystyle A\rightarrow b}$

  after that ${\displaystyle A\rightarrow S}$

• ${\displaystyle S_{0}\rightarrow S}$
• ${\displaystyle S\rightarrow ASA|AS|SA|aB|a}$
• ${\displaystyle A\rightarrow ASA|AS|SA|aB|a|b}$
• ${\displaystyle B\rightarrow b}$

  and finally ${\displaystyle S_{0}\rightarrow S}$

• ${\displaystyle S_{0}\rightarrow ASA|AS|SA|aB|a}$
• ${\displaystyle S\rightarrow ASA|AS|SA|aB|a}$
• ${\displaystyle A\rightarrow ASA|AS|SA|aB|a|b}$
• ${\displaystyle B\rightarrow b}$

  4. Longer concatenations are not allowed, so we introduce an additional variable and replace it with the rule and : ${\displaystyle A_{1}}$ ${\displaystyle S\rightarrow ASA}$ ${\displaystyle S\rightarrow AA_{1}}$ ${\displaystyle A_{1}\rightarrow SA}$

• ${\displaystyle S_{0}\rightarrow AA_{1}|AS|SA|aB|a}$
• ${\displaystyle S\rightarrow AA_{1}|AS|SA|aB|a}$
• ${\displaystyle A\rightarrow AA_{1}|AS|SA|aB|a|b}$
• ${\displaystyle A_{1}\rightarrow SA}$
• ${\displaystyle B\rightarrow b}$

  Now only the rule and . Therefore, another variable is used which, together with the rule , can replace the terminal symbol in the rules mentioned. ${\displaystyle A\rightarrow aB}$ ${\displaystyle S\rightarrow aB}$ ${\displaystyle X_{a}}$ ${\displaystyle X_{a}\rightarrow a}$ ${\displaystyle a}$

• ${\displaystyle S_{0}\rightarrow AA_{1}|AS|SA|X_{a}B|a}$
• ${\displaystyle S\rightarrow AA_{1}|AS|SA|X_{a}B|a}$
• ${\displaystyle A\rightarrow AA_{1}|AS|SA|X_{a}B|a|b}$
• ${\displaystyle A_{1}\rightarrow SA}$
• ${\displaystyle X_{a}\rightarrow a}$
• ${\displaystyle B\rightarrow b}$

  Thus the grammar is converted to Chomsky normal form.

swell

• Grzegorz Rozenberg, Arto Salomaa: Handbook of Formal Languages . Volume 1: Word, Language, Grammar. Springer-Verlag, Berlin et al. 1997, ISBN 3-540-60420-0 , pp. 124-125