Máquina de Turing

AFND, Máquina de Turing com pilha

Benefícios

Pâmela Dias Carvalho

Resumo:

O Modelo matemático Autômato Finito utilizando pilha, somente poderá ser AFND ( Autômato Finito não Determinístico) com a pilha dá ao AFND mais liberdade para ler a classe das linguagens livres de contexto.

Maquina de Turing

I. Introdução:

O presente trabalho visa, estruturá os benefícios de se utilizar pilha no modelo matemático: Autômato Finito não Determinístico, juntamente com a Máquina de Turing, conceituando, demonstrando, enumerando os benefícios de se utilizar esse tipo.

II. Autômato de Pilha

Os Autômatos de pilha reconhecem as Linguagens livre de contexto, de acordo com a hierarquia de Chomsky basicamente é um AFND incluindo uma pilha como memória auxiliar, ela é independente da fita de entrada e não possui limite máximo de tamanho, ela pode ser lida e alterada durante um processamento.

III. Definição Formal

Um autômato com pilha é uma sêxtupla = onde:

FIGURA 01:

Na figura acima, ilustra a fita de entrada, a função de transição, como será feito a ocupação na pilha.

Um autômato com pilha é composto basicamente, por quatro partes

a) Fita, análoga à do autômato finito

b) Pilha, memória auxiliar que pode ser usada livremente para leitura (pop) e gravação (push).

c) Unidade de controle: Reflete o estado corrente da máquina, possui um cabeçote de fita e um cabeçote pilha.

d) Programa ou Função de Transição: Comanda a leitura da fita, leitura e gravação da pilha e define o estado da máquina.

As seguintes características de um AP devem ser consideradas.

• A função pode ser indefinida em algumas circunstancias;

• O símbolo l na gravação ou leitura indica que nenhuma gravação ou leitura será realiza na pilha.

FIGURA 02:

A figura acima é um exemplo onde projeta um AP, suas funções de transições utilizadas, como ficará a escrita na pilha, a entrada lida, e o estado em que se encontra.

Se permitíssemos que um Autômato Finito tivesse acesso à duas pilhas ao invés de apenas uma, obtemos um dispositivo ainda mais poderoso, com poder equivalente ao de uma Máquina de Turing.

Com o uso de pilhas o autômato fica mais poderoso, podendo ler mais classes de gramáticas, e com a fita auxiliando com uma “memória”.