Forme normale de Kuroda

En informatique théorique, et particulièrement en théorie des langages formels, une grammaire contextuelle est dite en forme normale de Kuroda si ses règles de production sont de l'une des formes suivantes :

$AB\to CD$

$A\to BC$

$A\to B$

$A\to a$

où $A,B,C$ et $D$ sont des symboles non terminaux et $a$ est un symbole terminal. Certains auteurs omettent dans la définition les règles de renommage de la forme $A\to B$.

La forme normale porte le nom de Sige-Yuki Kuroda, qui appelait ces grammaires des grammaires linéaires bornées — une terminologie qui a également été utilisée par d'autres auteurs par la suite.

Une grammaire sous forme normale de Kuroda est non contractante et engendre donc un langage contextuel. Inversement, tout langage contextuel qui n'engendre pas la chaîne vide peut être engendré par une grammaire en forme normale de Kuroda.

Une technique simple, attribuée à György Révész, pour mettre une grammaire quadratique de Chomsky en forme de Kuroda est la suivante : une règle $AB\to CD$ est remplacée par quatre règles contextuelles $AB\to AZ$, $AZ\to WZ$, $WZ\to WD$ et $WD\to CD$. Cette technique donne également une preuve de ce que toute grammaire non contractante est sensible au contexte.

Il existe également une forme normale similaire pour les grammaires non expansive, et que certains auteurs appellent également la « forme normale de Kuroda » . Les règles sont alors :

$AB\to CD$

$A\to BC$

$A\to a$

$A\to \varepsilon$

où $\varepsilon$ est la chaîne vide. Toute grammaire générale est faiblement équivalente à une grammaire utilisant uniquement des productions de cette forme. Si la règle $AB\to CD$ est omise dans ce qui précède, on obtient des langages context-free.

La forme normale de Penttonen (pour les grammaires générales) est le cas particulier où la première règle ci-dessus est de la forme $AB\to AD$. De même, pour les grammaires contextuelles, la forme normale de Penttonen, également appelée forme normale unilatère selon la propre terminologie de Penttonen est la suivante :

$AB\to AD$

$A\to BC$

$A\to a$

Pour toute grammaire contextuelle, il existe une forme normale unilatère faiblement équivalente.

Articles liés

• Forme de Backus – Naur
• Forme normale de Chomsky
• Forme normale de Greibach

Articles complémentaires

• Sige-Yuki Kuroda, « Classes of languages and linear-bounded automata », Information and Control, vol. 7,‎ juin 1964, p. 207–223 (DOI 10.1016/S0019-9958(64)90120-2)
• György Révész, « Comment on the paper "Error detection in formal languages" », Journal of Computer and System Sciences, vol. 8, n^o 2,‎ 1974, p. 38–242 (DOI 10.1016/S0022-0000(74)80057-7) (« Révész' trick »)
• Martti Penttonen, « One-sided and two-sided context in formal grammars », Information and Control, vol. 25, n^o 4,‎ août 1974, p. 371–392 (DOI 10.1016/S0019-9958(74)91049-3)