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^[1] :

${\displaystyle AB\to CD}$

${\displaystyle A\to BC}$

${\displaystyle A\to B}$

${\displaystyle A\to a}$

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

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^[3].

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^[2].

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 ${\displaystyle AB\to CD}$ est remplacée par quatre règles contextuelles ${\displaystyle AB\to AZ}$, ${\displaystyle AZ\to WZ}$, ${\displaystyle WZ\to WD}$ et ${\displaystyle WD\to CD}$. Cette technique donne également une preuve de ce que toute grammaire non contractante est sensible au contexte^[1].

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

${\displaystyle AB\to CD}$

${\displaystyle A\to BC}$

${\displaystyle A\to a}$

${\displaystyle A\to \varepsilon }$

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

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 ${\displaystyle AB\to AD}$^[4]. 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^[1],[2] la suivante :

${\displaystyle AB\to AD}$

${\displaystyle A\to BC}$

${\displaystyle A\to a}$

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

Articles liés

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

Références

1. Masami Ito, Yūji Kobayashi et Kunitaka Shoji, Automata, Formal Languages and Algebraic Systems: Proceedings of AFLAS 2008, Kyoto, Japan, 20-22 September 2008, World Scientific, 2010 (ISBN 978-981-4317-60-3, présentation en ligne), p. 182
2. Alexandru Mateescu et Arto Salomaa, « Chapter 4 : Aspects of Classical Language Theory », dans Handbook of Formal Languages. Volume I: Word, language, grammar, Springer-Verlag, 1997 (ISBN 978-3-540-61486-9), p. 190.
3. Willem J. M. Levelt, An Introduction to the Theory of Formal Languages and Automata, John Benjamins Publishing, 2008 (ISBN 978-90-272-3250-2, lire en ligne), p. 126–127.
4. Alexander Meduna, Automata and Languages: Theory and Applications, Springer Science & Business Media, 2000 (ISBN 978-1-85233-074-3, lire en ligne), p. 722-728.

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)