Système de Post

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 ${\displaystyle [}$ et ${\displaystyle ]}$;
• L'ensemble qui contient le mot []comme seul mot initial ;
• Les trois règles de production suivantes :

1. ${\displaystyle X\to [X]}$
2. ${\displaystyle X\to XX}$
3. ${\displaystyle X_{1}X_{2}\to X_{1}[\ ]X_{2}}$

Voici quelques mots dérivés :

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

• ${\displaystyle A}$ est un alphabet fini ;
• ${\displaystyle I}$ est un ensemble fini de mots initiaux sur l'alphabet ${\displaystyle A}$ ;
• ${\displaystyle 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 :

${\displaystyle g_{1},\ldots ,g_{k}\to h}$

où ${\displaystyle g_{1},\ldots ,g_{k}}$ et ${\displaystyle h}$ sont des mots fixes contenant des variables, notées ${\displaystyle X_{i,j}}$ et ${\displaystyle Y_{k}}$ respectivement, de la forme

${\displaystyle g_{i}=g_{i0}X_{i1}g_{i1}X_{i2}g_{i2}\cdots X_{im_{i}}g_{im_{i}}}$

et

${\displaystyle h=h_{0}Y_{1}h_{1}Y_{2}h_{2}\cdots Y_{n}h_{n}}$.

Les mots ${\displaystyle g_{i}}$ sont appelés les antécédents, le mot ${\displaystyle h}$ le conséquent de la règle. La condition requise est que chaque ${\displaystyle Y_{k}}$ dans le conséquent figure parmi les variables ${\displaystyle 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[1], auquel cas elle s'écrit plus simplement

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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[2] 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 ${\displaystyle A}$.

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

${\displaystyle gX\ \rightarrow \ Xh}$

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

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.

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

${\displaystyle X_{1}gX_{2}\ \rightarrow \ X_{1}hX_{2}}$

Les productions sont des règles de substitution, aussi écrites sous la forme ${\displaystyle 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.

• Emil Post, « Formal Reductions of the General Combinatorial Decision Problem », American Journal of Mathematics, vol. 65, n^o 2,‎ 1943, p. 197-215.
• Marvin Minsky, Computation : Finite and Infinite Machines, Prentice-Hall, 1967, 317 p. (ISBN 978-0-13-165563-8).
• Dexter C. Kozen, Automata and Computability, Springer, coll. « Undergraduate Texts in Computer Science », 1997, 400 p. (ISBN 978-0-387-94907-9, lire en ligne).

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