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].

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.