Sistema canônico de Post

Um sistema canônico de Post, como criado por Emil Post, é um sistema de manipulação de cadeias que começa com uma quantidade finita de cadeias e repetidamente as transforma aplicando um conjunto finito J de regras especificadas de uma certa forma, assim gerando uma linguagem formal. Hoje eles possuem uma relevância mais histórica porque todo sistema canônico de Post pode ser reduzido a um sistema de reescrita de cadeias (sistemas de Thue-Semi), o que é uma formulação mais simples. Ambos os formalismos são Turing completos.

Definição

Um sistema canônico de Post é uma tripla (A,I,R), onde

• A é um alfabeto finito, e finitas (possivelmente vazias) cadeias em A são chamadas palavras.
• I é um conjunto finito de palavras iniciais.
• R é um conjunto finito de regras de transformação de cadeias (chamadas regras de produção), cada regra sendo da seguinte forma:

${\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 }}}$

onde cada g e h é uma palavra fixa específica, e cada $ e $'  é uma variável servindo como uma palavra arbitrária. As cadeias antes e depois da seta em uma regra de produção são chamadas os antecedentes e consequentes da regra, respectivamente. É preciso que cada  $'  nos consequentes seja um dos $s nos antecedentes desta regra, e cada antecedente e consequente conterem ao menos uma variável.

Em vários contextos, cada regra de produção tem apenas um antecedente, tomando a forma mais simples

$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}$

A linguagem formal gerada por um sistema canônico de Post é o conjunto cujos elementos são as palavras iniciais juntas com todas as palavras obteníveis a partir delas através da aplicação repetida das regras de produção. Tais conjuntos são recursivamente enumeráveis e toda linguagem recursivamente enumerável é a restrição de algum conjunto deste tipo para um sub-alfabeto de A.

Exemplo (expressões de colchetes bem formadas)

Alfabeto: {[, ]}
Palavra inicial: []
Regras de produção: 
(1)       $ → [$]
(2)       $ → $$
(3)       $1[]$2 → $1$2

Derivação de algumas palavras na linguagem de expressões de colchetes bem formadas:

       []             initial word
       [][]           by (2)
       [[][]]         by (1)
       [[][]][[][]]   by (2)
       [[][]][][[][]] by (3)
       ...

Teorema da forma normal

Diz-se que um sistema canônico de Post está na forma normal se ele só possui uma palavra inicial e toda regra de produção é da forma simples

$g\$\ \rightarrow \ \$h$

Post provou o notável Teorema da forma normal em 1943, o qual se aplica ao sistema de Post mais genérico:

Dado qualquer sistema canônico de Post sobre um alfabeto A, um sistema canônico de Post na forma normal pode ser construído a partir dele, possivelmente ampliando o alfabeto, tal que o conjunto de palavras envolvendo apenas letras de A que são formados pelo sistema em forma normal é exatamente o conjunto de palavras gerado pelo sistema original.

Sistemas de etiquetamento, os quais abrangem um modelo computacional universal, são exemplos notáveis de sistemas de Post em forma normal, sendo também monogênicos (um sistema canônico é dado como monogênico se, dada qualquer cadeia, no máximo uma nova cadeia pode ser produzida a partir dela em um passo — i.e., o sistema é determinístico).

Sistemas de reescrita de cadeias, gramáticas formais tipo-0

Um sistema de reescrita de cadeias é um tipo especial de sistema canônico de Post com uma única palavra inicial, e as produções são cada uma da forma

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

Isto é, cada regra de produção é uma regra de substituição simples, geralmente escrita na forma g → h. Foi provado que qualquer sistema canônico de Post é redutível para um sistema de substituição, o qual, enquanto gramática formal, também é chamado de gramática de frase-estrutura, ou uma gramática tipo-0 na hierarquia de Chomsky.

Referências

• Emil Post, "Formal Reductions of the General Combinatorial Decision Problem," American Journal of Mathematics 65 (2): 197-215, 1943.
• Marvin Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., N.J., 1967.