Un sistema Post canónico , 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 forma determinada, generando así un lenguaje formal . Hoy en día son principalmente de relevancia histórica porque cada sistema Post canónico puede reducirse 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 poscanó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:
donde cada g y h es un especificado fijo palabra, y cada uno $ y $' es una variable de pie para 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 $ s 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
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 de ellas mediante la aplicación repetida de las reglas de producción. Tales conjuntos son recursivamente enumerables lenguas y cada lengua recursivamente numerable es la restricción de algunos de estos conjuntos a un sub-alfabeto de la A .
Ejemplo (expresiones de corchetes bien formados)
Alfabeto: {[, ]}Palabra inicial: []Reglas de producción: (1) $ → [ $ ](2) $ → $$ (3) $ 1 $ 2 → $ 1 [] $ 2Derivación de algunas palabras en el lenguaje de expresiones de corchetes bien formados: [] palabra inicial [] [] por (2) [[][]] por 1) [[] []] [[] []] por (2) [[] []] [] [[] []] por (3) ...
Teorema de forma normal
Se dice que un sistema poscanónico está en forma normal si solo tiene una palabra inicial y cada regla de producción es de la forma simple
Post 1943 demostró el notable Teorema de la forma normal , que se aplica al tipo más general de sistema Post canónico:
- Dado cualquier sistema canónico Post en un alfabeto A , se puede construir un sistema canónico Post en forma normal a partir de él, posiblemente agrandando el alfabeto, de modo que el conjunto de palabras que involucran solo letras de A que son generadas por el sistema de forma normal es exactamente el conjunto de palabras generado por el sistema original.
Los sistemas de etiquetas , que comprenden un modelo computacional universal, son ejemplos notables de sistema Post-forma normal, que también es monogénico . (Se dice que un sistema canónico es monogénico si, dada cualquier cuerda, como máximo se puede producir una nueva cuerda en un solo 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 canónico Post con una sola palabra inicial, y las producciones son cada una de las formas
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 se puede reducir 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.