Sistema postcanónico

Un sistema postcanónico , también conocido como sistema de postproducció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 mediante la aplicación de un conjunto finito j de reglas específicas de una forma determinada, generando así un lenguaje formal . Hoy en día, tienen principalmente relevancia histórica porque cada sistema postcanónico se puede reducir a un sistema de reescritura de cadenas (sistema semi-Thue), que es una formulación más simple. Ambos formalismos son Turing completos .

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) en 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 $' en el consecuente sea uno de los $ en los antecedentes de esa regla, y que cada antecedente y consecuente contenga al menos una variable.

En muchos contextos, cada regla de producción tiene solo un 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 postcanó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 alguno de dichos conjuntos 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 postcanónico está en forma normal si tiene solo una palabra inicial y cada regla de producción es de la forma simple

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

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

Dado cualquier sistema postcanónico sobre un alfabeto A , se puede construir a partir de él un sistema postcanónico en forma normal , posiblemente ampliando el alfabeto, de modo que el conjunto de palabras que involucran solo letras de A que son generadas por el sistema de 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, que también son monogénicos . (Se dice que un sistema canónico es monogénico si, dada una cadena cualquiera, se puede producir como máximo una nueva cadena a partir de ella en un paso, es decir, el sistema es determinista).

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

Un sistema de reescritura de cadenas es un tipo especial de sistema postcanó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 postcanó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., NJ, 1967.