Kuroda normal form

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In formal language theory, a noncontracting grammar is in Kuroda normal form if all production rules are of the form: :AB → CD or :A → BC or :A → B or :A → a where A, B, C and D are nonterminal symbols and a is a terminal symbol. Some sources omit the A → B pattern.

It is named after Sige-Yuki Kuroda, who originally called it a linear bounded grammar, a terminology that was also used by a few other authors thereafter. Every grammar in Kuroda normal form is noncontracting, and therefore, generates a context-sensitive language. Conversely, every noncontracting grammar that does not generate the empty string can be converted to Kuroda normal form.

A straightforward technique attributed to György Révész transforms a grammar in Kuroda normal form to a context-sensitive grammar: AB → CD is replaced by four context-sensitive rules AB → AZ, AZ → WZ, WZ → WD and WD → CD. This proves that every noncontracting grammar generates a context-sensitive language.

There is a similar normal form for unrestricted grammars as well, which at least some authors call "Kuroda normal form" too: :AB → CD or :A → BC or :A → a or :A → ε where ε is the empty string. Every unrestricted grammar is weakly equivalent to one using only productions of this form.

If the rule AB → CD is eliminated from the above, one obtains context-free grammars in Chomsky Normal Form.…

In formal language theory, a noncontracting grammar is in Kuroda normal form if all production rules are of the form: AB → CD or A → BC or A → B or A → a where A, B, C and D are nonterminal symbols and a is a terminal symbol. Some sources omit the A → B pattern.

It is named after Sige-Yuki Kuroda, who originally called it a linear bounded grammar, a terminology that was also used by a few other authors thereafter. Every grammar in Kuroda normal form is noncontracting, and therefore, generates a context-sensitive language. Conversely, every noncontracting grammar that does not generate the empty string can be converted to Kuroda normal form.

A straightforward technique attributed to György Révész transforms a grammar in Kuroda normal form to a context-sensitive grammar: AB → CD is replaced by four context-sensitive rules AB → AZ, AZ → WZ, WZ → WD and WD → CD. This proves that every noncontracting grammar generates a context-sensitive language.

There is a similar normal form for unrestricted grammars as well, which at least some authors call "Kuroda normal form" too: AB → CD or A → BC or A → a or A → ε where ε is the empty string. Every unrestricted grammar is weakly equivalent to one using only productions of this form. If the rule AB → CD is eliminated from the above, one obtains context-free grammars in Chomsky Normal Form.

The Penttonen normal form (for unrestricted grammars) is a special case where first rule above is AB → AD. Similarly, for context-sensitive grammars, the Penttonen normal form, also called the one-sided normal form (following Penttonen's own terminology) is: AB → AD or A → BC or A → a For every context-sensitive grammar, there exists a weakly equivalent one-sided normal form.

See also

Backus–Naur form Chomsky normal form Greibach normal form

Further reading

G. Révész, "Comment on the paper 'Error detection in formal languages,'" Journal of Computer and System Sciences, vol. 8, no. 2, pp. 238–242, Apr. 1974. (Révész' trick)

Text derived from https://en.wikipedia.org/w/index.php?oldid=1157000774 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001157000774 · captured 1685030554.0 · version history

Cite this page as: encyclopegia.org, “Kuroda normal form”, snapshot enwiki-001157000774. https://encyclopegia.org/a/kuroda-normal-form

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.