Kuroda-Normalform

The Kuroda normal form is a term of theoretical computer science, which is associated with context-sensitive languages ​​of interest. It is named after the linguist Sige - Yuki Kuroda and describes a normal form of the monotone grammars, that is a subset of the monotone grammars, which loses none of expressiveness with respect to the set of all monotone grammars. The importance of the Kuroda normal form is the very simple structure of the productions. Because monotone grammars and context-sensitive grammars are sometimes indistinguishable, the Kuroda normal form is also called the normal form of context-sensitive grammars.

The Kuroda normal form is a generalization of Chomsky Normal Form, which is a normal form for context-free grammars.

Definition

A formal grammar is in Kuroda normal form ( CNF short ) if all productions are of the form:

Where, , and are variables, and a terminal symbol.

If the second and fourth normal form does not happen, the grammar is in Chomsky normal form.

Properties

• Each grammar in Kuroda normal form is a monotonic grammar.
• For each monotonic grammar exists a monotonic grammar Kuroda normal form, generating the same language, that is,. is then called a Kuroda normal form of the monotone grammar.

Transformation of a grammar in Kuroda normal form

Be a monotonic grammar. A Kuroda normal form of can be constructed:

• All in occurring terminal symbols are each replaced by a new variable, and for each terminal symbol, the new productions will be introduced.
• Each production of the form is replaced by the following new productions:, for all and. Here are new variables.
• Each production of the form, with one replaced by the following new productions: for all: for all: and. Here are new variables.

The grammar thus generated is in Kuroda normal form and produces the same language as the grammar before.

Revesz normal form

Each monotone grammar in Kuroda normal form can be converted into a context-sensitive grammar in Revesz normal form. These two new nonterminals are for each production rule of the form introduced and the rule replaced by four rules:

A context-sensitive grammar is in Revesz - normal form if all productions are of the form:

Here are, and variables and is a terminal symbol.

For each context-sensitive grammar exists a context sensitive grammar in Kuroda normal form that generates the same language, that is,.