Kuroda normal form
In formal language theory, a noncontracting grammar is in Kuroda normal form if all production rules are of the form:<ref name="ItoKobayashi2010"/>
- 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.<ref name="ItoKobayashi2010"/> Some sources omit the A → B pattern.<ref name="MS190"/>
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.<ref>Template:Cite book</ref>
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.<ref name="MS190">Template:Cite book</ref>
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.<ref name="ItoKobayashi2010">Template:Cite book</ref>
There is a similar normal form for unrestricted grammars as well, which at least some authors call "Kuroda normal form" too:<ref name="Meduna2000-722"/>
- 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.<ref name="MS190"/>
If the rule AB → CD is eliminated from the above, one obtains context-free grammars in Chomsky Normal Form.<ref name="Meduna2000-728">Template:Cite book</ref> The Penttonen normal form (for unrestricted grammars) is a special case where first rule above is AB → AD.<ref name="Meduna2000-722">Template:Cite book</ref> Similarly, for context-sensitive grammars, the Penttonen normal form, also called the one-sided normal form (following Penttonen's own terminology) is:<ref name="ItoKobayashi2010"/><ref name="MS190"/>
- AB → AD or
- A → BC or
- A → a
For every context-sensitive grammar, there exists a weakly equivalent one-sided normal form.<ref name="MS190"/>
See alsoEdit
ReferencesEdit
Further readingEdit
- Template:Cite journal
- 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. {{#invoke:doi|main}} (Révész' trick)
- Template:Cite journal