Sistema poscanónico

Un sistema poscanónico , también conocido como sistema de posproducción , creado por Emil Post , es un sistema de manipulación de cadenas que comienza con un número finito de cadenas y las transforma repetidamente aplicando un conjunto finito j de reglas específicas de una determinada forma. generando así un lenguaje formal . Hoy en día tienen principalmente relevancia histórica porque cada sistema poscanónico puede reducirse a un sistema de reescritura de cadenas (sistema semi-Thue), que es una formulación más simple. Ambos formalismos son completos de Turing .

Definición

Un sistema postcanónico es un triplete ( A , I , R ), donde

• A es un alfabeto finito y las cadenas finitas (posiblemente vacías) de A se denominan palabras .
• I es un conjunto finito de palabras iniciales .
• R es un conjunto finito de reglas de transformación de cadenas (llamadas reglas de producción ), cada regla tiene la siguiente forma:

${\displaystyle {\overset {\begin{matrix}g_{10}&\$_{11}&g_{11}&\$_{12}&g_{12}&\dots &\$_{1m_{1}}&g_{1m_{1}}\\g_{20}&\$_{21}&g_{21}&\$_{22}&g_{22}&\dots &\$_{2m_{2}}&g_{2m_{2}}\\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\g_{k0}&\$_{k1}&g_{k1}&\$_{k2}&g_{k2}&\dots &\$_{km_{k}}&g_{km_{k}}\\\end{matrix}}{\underset {\begin{matrix}h_{0}&\$'_{1}&h_{1}&\$'_{2}&h_{2}&\dots &\$'_{n}&h_{n}\\\end{matrix}}{\downarrow }}}}$

donde cada g y h es una palabra fija especificada , y cada $ y $' es una variable que representa una palabra arbitraria. Las cadenas antes y después de la flecha en una regla de producción se denominan antecedentes y consecuentes de la regla , respectivamente. Se requiere que cada $' del consecuente sea uno de los $ s de los antecedentes de esa regla, y que cada antecedente y consecuente contengan al menos una variable.

En muchos contextos, cada regla de producción tiene un solo antecedente, por lo que toma la forma más simple

${\displaystyle g_{0}\ \$_{1}\ g_{1}\ \$_{2}\ g_{2}\ \dots \ \$_{m}\ g_{m}\ \rightarrow \ h_{0}\ \$'_{1}\ h_{1}\ \$'_{2}\ h_{2}\ \dots \ \$'_{n}\ h_{n}}$

El lenguaje formal generado por un sistema poscanónico es el conjunto cuyos elementos son las palabras iniciales junto con todas las palabras que se pueden obtener a partir de ellas mediante la aplicación repetida de las reglas de producción. Dichos conjuntos son lenguajes recursivamente enumerables y cada lenguaje recursivamente enumerable es la restricción de algún conjunto de este tipo a un subalfabeto de A.

Ejemplo (expresiones entre paréntesis bien formadas)

Alfabeto: {[, ]}Palabra inicial: []Reglas de producción:(1) $ → [ $ ](2) $ → $$
(3) $ 1 $ 2 → $ 1 [] $ 2Derivación de algunas palabras en el lenguaje de expresiones entre paréntesis bien formadas: [] palabra inicial [][] por (2) [[][]] por 1) [[][]][[][]] por (2) [[][]][][[][]] por (3) ...

Teorema de la forma normal

Se dice que un sistema poscanónico está en forma normal si tiene una sola palabra inicial y cada regla de producción es de la forma simple.

${\displaystyle g\$\ \rightarrow \ \$h}$

Después de 1943 demostró el notable teorema de la forma normal , que se aplica al tipo más general de sistema poscanónico:

Dado cualquier sistema poscanónico en un alfabeto A , se puede construir un sistema poscanónico en forma normal a partir de él, posiblemente ampliando el alfabeto, de modo que el conjunto de palabras que involucran solo letras de A que son generadas por el sistema en forma normal sea exactamente el conjunto de palabras generadas por el sistema original.

Los sistemas de etiquetas , que comprenden un modelo computacional universal, son ejemplos notables de sistemas de forma posnormal, siendo también monogénicos . (Se dice que un sistema canónico es monogénico si, dada cualquier cadena, se puede producir como máximo una nueva cadena a partir de ella en un solo paso; es decir, el sistema es determinista).

Sistemas de reescritura de cadenas, gramáticas formales tipo 0

Un sistema de reescritura de cadenas es un tipo especial de sistema poscanónico con una sola palabra inicial, y las producciones son cada una de la forma

${\displaystyle P_{1}gP_{2}\ \rightarrow \ P_{1}hP_{2}}$

Es decir, cada regla de producción es una regla de sustitución simple, a menudo escrita en la forma g → h . Se ha demostrado que cualquier sistema poscanónico es reducible a un sistema de sustitución de este tipo , que, como gramática formal , también se denomina gramática de estructura sintagmática o gramática de tipo 0 en la jerarquía de Chomsky .

Referencias

• Emil Post , "Reducciones formales del problema de decisión combinatoria general", American Journal of Mathematics 65 (2): 197-215, 1943.
• Marvin Minsky , Computación: máquinas finitas e infinitas , Prentice-Hall, Inc., Nueva Jersey, 1967.