Système de Post

En informatique théorique et en logique mathématique, un système de Post, ou système canonique de Post, appelé ainsi d’après son créateur Emil Post, est un système de manipulation de chaînes de caractères qui commence avec un nombre fini de mots et les transforme par application d’un ensemble fini de règles d’une forme particulière, et par là engendre un langage formel. Ces système ont surtout un intérêt historique car tout système de Post peut être réduit à un système de réécriture de mots (un système de semi-Thue) qui est une formulation plus simple. Les deux formalismes -- système de Post et réécriture -- sont Turing-complets.

Un exemple : les expressions bien parenthésées

Un système de Post est la donnée d'un alphabet, un ensemble de mots initiaux et de règles de production. Par exemple :

• Un alphabet constitué des deux caractères $[$ et $]$;
• L'ensemble qui contient le mot []comme seul mot initial ;
• Les trois règles de production suivantes :

1. $X\to [X]$
2. $X\to XX$
3. $X_1{X}_2\to X_1[]X_2$

Voici quelques mots dérivés :

[]	mot initial
[][]	obtenu par la règle 2.
[[][]]	obtenu par la règle 1.
[[][]][[][]]	obtenu par la règle 2.
[[][]][][[][]]	obtenu par la règle 3.

Définition formelle

Un système canonique de Post est un triplet $(A,I,R)$, où

• $A$ est un alphabet fini ;
• $I$ est un ensemble fini de mots initiaux sur l'alphabet $A$ ;
• $R$ est un ensemble fini de règles de transformation de mots, appelées règles de production.

Chaque règle est de la forme :

$g_1,\dots ,g_k\to h$

où $g_1,\dots ,g_k$ et $h$ sont des mots fixes contenant des variables, notées $X_{i,j}$ et $Y_k$ respectivement, de la forme

$g_i=g_{i0}{X}_{i1}{g}_{i1}{X}_{i2}{g}_{i2}\cdots X_{i{m}_i}{g}_{i{m}_i}$

et

$h=h_0{Y}_1{h}_1{Y}_2{h}_2\cdots Y_n{h}_n$.

Les mots $g_i$ sont appelés les antécédents, le mot $h$ le conséquent de la règle. La condition requise est que chaque $Y_k$ dans le conséquent figure parmi les variables $X_{i,j}$ des antécédents, et que chaque conséquent et antécédent contient au moins une variable.

En général, une règle de production ne contient qu'un seul antécédent, auquel cas elle s'écrit plus simplement

$g_0{X}_1{g}_1{X}_2{g}_2\cdots X_m{g}_m\to h_0{Y}_1{h}_1{Y}_2{h}_2\cdots Y_n{h}_n$.

On peut appliquer une règle à un mot $w$ s'il se factorise selon l'antécédent de la règle, en associant à chaque variable un facteur du mot. Le mot obtenue est alors celui où les variables du conséquent sont remplacées par les valeurs associées aux variables dans l'antécédent. Dans le cas de plusieurs antécédents, le mot $w$ doit se factoriser selon chacun des antécédents pour dériver le conséquent. Post lui-même a prouvé, preuve reprise dans le livre de Minsky a prouvé que l’on peut se contenter de règles avec un seul antécédent.

Le langage engendré par le système de Post est l’ensemble des mots composés des mots initiaux et des mots que l’on obtient par une application répétée de règles de production. Ces ensembles sont des langages récursivement énumérables et, réciproquement, tout langage récursivement énumérable est la restriction d’un tel ensemble à un sous-alphabet de $A$.

Théorème de forme normale

Un système de Post est en forme normale (normal form) si toutes ses règles sont de la forme

$gX\to Xh$

Les règles en forme normale consistent donc à enlever le préfixe $g$ au début d' un mot et d'ajouter le mot $h$ à la fin. Post a démontré en 1943 le théorème de forme normale suivant : Modèle:Théorème

Les systèmes de tague qui eux aussi sont un modèle de calcul universel, sont des exemples particuliers de systèmes de Post en forme normale ; ils sont de plus « monogènes » : Un système est dit monogène si, pour toute chaîne, il existe au plus un nouveau mot peut être produit, en d’autres termes, si le système est déterministe.

Systèmes de réécriture et grammaires de type 0

Un système de réécriture est un cas particulier d’un système de Post où les productions sont de la forme :

$X_{1}g{X}_2\to X_{1}h{X}_2$

Les productions sont des règles de substitution, aussi écrites sous la forme $g\to h$. On peut démontrer que tout système de Post peut être ramené à un tel système, qui est une grammaire formelle de type 0 dans la hiérarchie de Chomsky.

Bibliographie

• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Ouvrage.

Articles connexes

• Réécriture (informatique)
• Machine de Turing
• Système de tague
• Automate à file