Chomsky-Normalform

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

There is a grammar in Chomsky normal form for each context-free language. It can therefore be constructed of any context-free grammar a Chomsky normal form that generates the same language. The grammar is then also called a Chomsky normal form of context-free grammar.

Another normal form for context-free grammars is the Greibach normal form. An extension of the Chomsky normal form for context sensitive grammars represents the Kuroda normal form

Definition

A formal grammar is in Chomsky normal form if each production has one of the following forms:

Being, and non- terminal symbols are from and a terminal symbol is off. is the start symbol and the empty word. If the production is part of the grammar, then you must not be on the right side of a production.

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

Construction of a Chomsky normal form

If there is a context-free grammar, so you can generate that gradually a grammar in Chomsky normal form that generates the same language:

Example

It is the grammar over the alphabet with the rules

To bring normal form in Chomsky.

1 Add a new start variable

Remove 2 transitions

A new rule has been created, which in turn must be treated equally:

3 Remove all unit rules. These are and.

Then

And finally

4 Longer chains are not allowed, so we carry an additional variable and replaced by the rule:

Now just stay still the rule and. Therefore, a further variable is used which can replace the Terminal icon in the above rules together with the rule.

Thus, the grammar is written in Chomsky normal form.

Swell

  • Grzegorz Rozenberg, Arto Salomaa, Handbook of Formal Languages ​​. Volume 1: Word, Language, Grammar. Springer -Verlag, Berlin and others, 1997, ISBN 3-540-60420-0, pp. 124-125
  • Compiler
  • Theory of formal languages
Linguistics Greibach-Normalform Kuroda-Normalform Terminal and nonterminal symbols Empty string
185355
de