Máquina de Post
O que eu considero mais interessante (e importante) no estudo das máquinas abstratas é que para entendê-las basta lápis e papel. Não existe a necessidade, a não ser para facilitar os estudos, do uso do simulador, podemos criar nossos programas à moda antiga, como tudo realmente começou. No caso da Máquina de Post darei um exemplo a seguir.
Fluxograma Máquina de Post Duplo Balanceamento
Retirei esse programa do livro "Teoria da Computação - Máquinas Universais e Computabilidade (Volume 5 - 3ª edição, página 184). O programa verifica o duplo balanceamento de palavras formadas pelos símbolos a e b, ou seja verifica se uma palavra é do tipo aaabbb ou bbbaaa, mesma quantidade de um símbolo seguida pela mesma quantidade do outro símbolo. Clique para ampliar o fluxograma:
Executando o programa
Caso 1: ACEITA
A seguir, a execução do programa (através da fila) para a entrada X = aaabbb
a
|
a
|
a
|
b
| b | b |
Primeiramente, o símbolo auxiliar é concatenado no fim da fila da palavra X:
X = aaabbb#
a
|
a
|
a
|
b
| b | b | # |
O primeiro símbolo é lido, como era um símbolo esperado ele é apenas destruído sem ser concatenado no fim da fila, pois não será mais necessário, a fila fica assim:
X = aabbb#
a
|
a
|
b
|
b
| b | # |
O segundo símbolo foi lido, como agora estamos esperando um b, enviamos o símbolo lido para o fim da fila, pois posteriormente ele será usado:
X = abbb#a
a
|
b
|
b
|
b
| # | a |
Novamente:
X = bbb#aa
b
|
b
|
b
|
#
| a | a |
Opa, finalmente encontramos um símbolo b respectivamente ao símbolo a que destruímos anteriormente, até agora está tudo ok, então o símbolo é apenas apagado:
X = bb#aa
b
|
b
|
#
|
a
| a |
Agora o programa vai ler um por um dos símbolos restantes e enviar ao fim da fila, até encontrar o símbolo auxiliar:
X = b#aab
b
|
#
|
a
|
a
| b |
Agora a primeira varredura da palavra foi completa, verifique como ficamos com dois símbolos à menos, isso porque, para verificar se a palavra está correta, o programa retira um símbolo a e um símbolo b. A partir de agora, para manter a estrutura do tipo fila, o programa realiza varreduras circulares na palavra até não restar mais nenhum símbolo ou até que a entrada seja rejeitada:
X = #aabb
#
|
a
|
a
|
b
| b |
X = aabb#
a
|
a
|
b
|
b
| # |
X = abb#
a
|
b
|
b
|
#
|
X = bb#a
b
|
b
|
#
|
a
|
X = b#a
b
|
#
|
a
|
X = #ab
#
|
a
|
b
|
X = ab#
a
|
b
|
#
|
X = b#
b
|
#
|
Após realizar as varreduras necessárias e não ter entrado em nenhum caso de REJEITA, restou apenas o símbolo auxiliar:
X = #
#
|
Mesmo assim o programa vai tentar realizar mais uma varredura, apagando o símbolo auxiliar e o concatenando no fim da palavra novamente:
X = #
#
|
É agora que o programa entra no caso do aceita, pois ao tentar realizar essa última varredura ele encontra apenas o # o destrói e a palavra é aceita, deixando a fila vazia e o programa termina sua execução:
Caso ainda não tenha entendido, basta pensar exatamente como uma fila funciona, quando alguém se retira de uma fila, ou volta para o fim, ou vai embora. No caso da máquina de Post, quando um símbolo é lido ou ele vai para o fim da fila ou é destruído.
_________________________________________________________________________________
Caso 2: REJEITA
A seguir, a execução do programa (através da fila) para a entrada X = aaabb, entrada que deve ser rejeitada pois apresenta um símbolo b a menos do que deveria:
a
|
a
|
a
|
b
| b |
Primeiramente, o símbolo auxiliar é concatenado no fim da fila da palavra X:
X = aaabb#
a
|
a
|
a
|
b
| b | # |
O primeiro símbolo é lido, como era um símbolo esperado ele é apenas destruído sem ser concatenado no fim da fila, pois não será mais necessário, a fila fica assim:
X = aabb#
a
|
a
|
b
|
b
| # |
O segundo símbolo foi lido, como agora estamos esperando um b, enviamos o símbolo lido para o fim da fila, pois posteriormente ele será usado:
X = abb#a
a
|
b
|
b
|
#
| a |
Novamente:
X = bb#aa
b
|
b
|
#
|
a
| a |
Opa, finalmente encontramos um símbolo b respectivo ao símbolo a que destruímos anteriormente, até agora está tudo ok, então o símbolo é apenas apagado:
X = b#aa
b
|
#
|
a
|
a
|
Agora a primeira varredura da palavra foi completa, verifique como ficamos com dois símbolos à menos, isso porque, para verificar se a palavra está correta, o programa retira um símbolo a e um símbolo b. A partir de agora, para manter a estrutura do tipo fila, o programa realiza varreduras circulares na palavra até não restar mais nenhum símbolo ou até que a entrada seja rejeitada:
X = #aab
#
|
a
|
a
|
b
|
X = aab#
a
|
a
|
b
|
#
|
X = ab#
a
|
b
|
#
|
X = b#a
b
|
#
|
a
|
X = #a
#
|
a
|
X = a#
a
|
#
|
Como tínhamos um símbolo b a menos na palavra ele não vai encontrar o símbolo correspondente e vai entrar em um caso de REJEITA pois encontrou o símbolo auxiliar antes da hora:
X = #
#
|
ENTRADA REJEITADA!
_________________________________________________________________________________
Com isso, encerro as postagens sobre a Máquina de Post, se estiverem com dúvidas, comentem à vontade!
Não deixem de ler as demais postagens sobre a Máquina de Post:
1.Introdução, definição e funcionamento
2.Usando o Simulador da Máquina de Post
3.Executando um programa no Simulador de Máquina de Post
2.Usando o Simulador da Máquina de Post
3.Executando um programa no Simulador de Máquina de Post
Gostei. Muito bom. Difícil encontrar material hein?! Estou pesquisando ainda, mas seria legal encontrar códigos de implementaçoes da máquina em linguagens de programação...
ResponderExcluir