1.1. É uma máquina composta por fita, unidade de controle e programa. – Fita: dispositivo de entrada que contém a informação a ser processada – Unidade de Controle: reflete o estado corrente da máquina • Possui uma unidade de leitura (cabeça da fita) • Acessa uma célula da fita de cada vez • Movimenta-se exclusivamente para a direita – Programa • Comanda as leituras • Define o estado da máquina
2. Autômato Finito Não-Determinístico
2.1. – Idéia básica: o processamento de uma entrada resulta em um conjunto de novos estados – IMPORTANTE: o não-determinismo não aumenta o poder computacional, ou seja, o tipo de linguagem reconhecida. – Definição Formal: é uma 5-upla M = (∑, Q , δ , q 0, F) • ∑: alfabeto, símbolos de entrada • Q : conjunto finito de estados possíveis • δ : função programa δ : Q x ∑ → 2 Q • q0 : estado inicial • F: conjunto finito de estados finais
