Linguagens formais

GILIARD GODINHO

TRABALHO DE TEORIA DA COMPUTAÇÃO

CRICIÚMA, NOVEMBRO DE 2009.
GILIARD GODINHO

TRABALHO DE TEORIA DA COMPUTAÇÃO

Trabalho apresentado à disciplina de Teoria da Computação, solicitado pela Prof. Christine Vieira Scarpato.

CRICIÚMA, NOVEMBRO DE 2009.

1. AUTÔMATO DE PILHA

São formalismos (máquinas) capazes de reconhecer as Linguagens Livres de Contexto, possuem maior poder que os Autômatos Finitos, pois tem um “espaço de armazenamento” extra que é utilizado durante o processamento de uma cadeia. Possui uma pilha que caracteriza uma memória auxiliar onde pode-se inserir e remover informações mesmo poder de reconhecimento das GLC. [pic]

♦ AP ou AP Não-Determinístico ♦ Fita Análoga à do Autômato Finito

♦ Cabeça de Fita Unidade de leitura, possui acessa uma célula da fita de cada vez movimentado-se exclusivamente para a direita, e ainda pode-se testar se leu toda a entrada

♦ Cabeça da Pilha unidade de leitura e gravação leitura: move para baixo acessando um símbolo de cada vez (topo) exclui o símbolo lido e pode testar se a pilha está vazia

gravação: move para cima, sendo possível armazenar uma palavra composta por mais de um símbolo neste caso, o símbolo do topo é o mais à esquerda da palavra gravada.

♦ Programa ou Função de Transição • programa ∗ comanda a leitura da fita ∗ comanda a leitura e gravação da pilha ∗ define o estado da máquina

2. Alan Mathison Turing

Alan Mathison Turing nasceu em 23 de junho de 1912 em Londres, filho de um oficial britânico, Julius Mathison e Ethel Sara