Sistema canônico de Post
# Sistema canônico de Post
## 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.
    $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)
## 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}$