Definição

O que são Máquinas de Post?

Home

Definição

Download Implementações 

Links

 

Uma máquina de post consiste de duas partes:

Uma fila que é utilizada como entrada, saída e memória de trabalho. A fila não possui tamanho nem limites fixos. Seu comprimento é igual ao da palavra corrente armazenada.

Um programa que é uma sequência finita de instruções, representado como um diagrama de fluxos, no qual cada vértice é uma instrução. As instruções podem ser de quatro tipos: partida, parada, desvio e atribuição.

Definição: Uma máquina de Post é uma tripla M=(Σ,D,#) onde:

Σ= alfabeto de símbolos de entrada;                                                          

D= programa ou diagrama de fluxos construído a partir de componentes elementares denominados partida, parada, desvio, atribuição;                 

#= símbolo auxiliar;

Diagrama de fluxos:

i. Partida: existe somente uma instrução de início em um programa;          

ii. Parada: existe duas alternativas de instruções de parada em um progrma, uma de aceitação e outra de rejeição;                                          

iii. Desvio: denota o comando que lê o símbolo mais à esquerda da palavra, retirando o primeiro símbolo;                                                          

iii. Atribuição: é uma instrução de concatenação, gravando o símbolo indicado (pertence a Σ U {#}) à direita da palavra armazenada em uma variável (no fim da fila);

 

Para descrições das máquinas de post disponibilizadas na área de downloads, clique aqui.

 

Definição de Máquinas de Post proposta pelos Professores Tiaraju Diverio e Paulo Blauth Menezes da Universidade Federal do Rio Grande do Sul no documento "Máquinas Universais" disponivel aqui.