Máquina sem pilha

MÁQUINA FINITA SEM PILHA

UNIR - Fundação Universidade de Federal de Rondônia NUC – Núcleo de Ciências da Computação

Resumo

O objetivo principal deste trabalho é mostrar uma visão geral das máquinas sem pilha, mais comumente conhecidas como autômatos de estado finito. Palavras-chaves: sem pilha, autômato, finito. 1. INTRODUÇÃO Máquina finita sem pilha ou autômato finito é uma modelagem de um comportamento, composto por estados, transições e ações. Por não ter pilhas, sem memória auxiliar para armazenamento, possui um poder computacional restrito. Ainda assim é um modelo recorrente para muitos elementos importantes de hardware e software. 2. AUTÔMATO FINITO Este modelo matemático corresponde a um sistema com entradas e saídas discretas, no qual se assume um número finito e pré-definido de estados. Por ser finito, a execução não pode ser memorizada, levando o sistema a memorizar somente aquilo que é relevante. A vantagem de usar um número finito de estados é que é possível implementá-lo de uma forma simples em hardware como um circuito, ou em um software que possa tomar decisões examinando apenas um número limitado de dados ou a própria posição no código. Um autômato pode ser visto como uma máquina composta basicamente por três partes:

Figura 1 Autômato finito como uma máquina de controle finito

a) Fita: Dispositivo de entrada que contém a informação a ser processada. A fita é finita à esquerda e à direita. É dividida em células onde cada uma armazena um símbolo. Os símbolos pertencem a um alfabeto de entrada. Não é possível gravar sobre a fita. Não existe memória auxiliar. Inicialmente a palavra a ser processada, isto é, a informação de entrada ocupa toda a fita. b) Unidade de Controle: Reflete o estado corrente da máquina. Possui uma unidade de leitura (cabeça de leitura, que acessa uma unidade da fita de cada vez. Pode assumir um número finito e pré-definido de estados. Após cada leitura a cabeça move-se uma célula para a direita. c) Programa ou