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[modifier | modifier le code]

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 :

$X\to [X]$
$X\to XX$
$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[modifier | modifier le code]

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},\ldots ,g_{k}\to h

où $g_{1},\ldots ,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_{im_{i}}g_{im_{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^[1], 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^[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 $A$ .

Théorème de forme normale[modifier | modifier le code]

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

gX\ \rightarrow \ 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^[3] le théorème de forme normale suivant :

Théorème de forme normale de Post — Pour tout système de Post, il existe un système de Post en forme normale équivalent ; ce système peut être construit effectivement.

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[modifier | modifier le code]

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}gX_{2}\ \rightarrow \ X_{1}hX_{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.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Post canonical system » (voir la liste des auteurs).

↑ C’est la définition de Dexter Kozen (Kozen 1997, p. 256-257).
↑ Minsky 1967.
↑ Post 1943.

Bibliographie[modifier | modifier le code]

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

Articles connexes[modifier | modifier le code]

[1] C’est la définition de Dexter Kozen (Kozen 1997, p. 256-257).

[2] Minsky 1967.

[3] Post 1943.

[1]

[2]

[3]