Baixe o app para aproveitar ainda mais
Prévia do material em texto
Professor Me. Paulo David pd.mnpa@gmail.com Faculdade Maurício de Nassau Curso: Sistemas de Informação Disciplina: Linguagens Formais e Autômatos Professor: Me. Paulo Roberto Sousa David Máquina de Turing • A máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais (em 1936). • Num sentido preciso, é um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento (memória, estados e transições) e não à sua implementação física. • A Máquina de Turing é um formalismo muito simples, universalmente conhecido e provavelmente o mais usado como modelo teórico da computação. • Por definição, se uma linguagem é reconhecida por alguma máquina de Turing, ela é recursivamente enumerável ou do Tipo 0. • Em Matemática, Lógica e Ciência da Computação, uma linguagem recursivamente enumerável é um tipo de Linguagem formal (Tipo 0) que também é chamada de linguagem Turing-reconhecível. • Na Teoria da Computabilidade, tradicionalmente chamada Teoria da Recursão, um conjunto S de números naturais é chamado recursivamente enumerável, computavelmente enumerável, semi-decidível, demonstrável ou Turing- reconhecível, se é aceito por uma Máquina de Turing. • O modelo matemático conhecido como Máquina de Turing, consiste basicamente de três partes: Fita, Unidade de Controle e Programa ou Função de Transição. • A Fita é usada simultaneamente como dispositivo de entrada, saída e memória de trabalho. • A Unidade de Controle reflete o estado corrente da máquina (estado ativo). Possui uma unidade de leitura e gravação (cabeça da fita) a qual acessa uma célula da fita de cada vez e movimenta-se para a esquerda ou direita. • O Programa, Função Programa ou Função de Transição é uma função que comanda as leituras e gravações, o sentido de movimento da cabeça e define o estado da máquina. Observação: • A fita é finita à esquerda e infinita à direita (tão grande quanto necessário), sendo dividida em células, cada uma armazenando um símbolo, que podem: ✓ Pertencer ao alfabeto de entrada. ✓ Pertencer ao alfabeto auxiliar. ✓ Ser “branco”. ✓ Ser “marcador de inicio de fita”. Configuração Inicial • Inicialmente, a palavra a ser processada (ou seja, a informação de entrada para a máquina) ocupa as células mais à esquerda após o marcador de inicio da fita, ficando as demais com “branco”. Configuração Inicial a b b c Fita Marcador de inicio da Fita Entrada Branco Unidade de Controle Posiciona na Cabeça da FitaControle ... Definição: Uma Máquina de Turing (MT) é uma 8-upla M = (K,Σ, , q0, F, V, ,). onde: • K (ou Q) é um conjunto finito não vazio de estados. • Σ é o alfabeto de entrada. • é uma função programa, função de transição. • qo (ou s) ∈ K é o estado inicial do autômato. • F⊂ K é o conjunto de estados finais (aceitação). • V é um alfabeto auxiliar (pode ser vazio). • é o símbolo espacial branco. • (ou ) é o símbolo de início ou marcador de início da fita. Observações • O símbolo de início de fita ocorre exatamente uma vez e na célula mais à esquerda da fita, auxiliando na identificação de que a cabeça da fita encontra-se na célula mais à esquerda da fita. • A função programa considera o estado corrente (ativo) e o símbolo lido da fita para determinar o novo estado, o símbolo a ser gravado e o sentido de movimento da cabeça, sendo que esquerda e direita serão representados por E e D, respectivamente. • A função programa pode ser interpretada como um diagrama, como ilustrado na figura a seguir. Supondo a transição (p,x)=(q,y,m). (x, y, m) p q Estado Anterior Novo Estado Símbolo lido da Fita (entrada) Sentido de Movimento Símbolo Gravado Computação • A computação de uma Máquina de Turing M, para uma palavra de entrada w, consiste na sucessiva aplicação da função programa a partir do estado inicial e da cabeça posicionada na célula mais à esquerda fita até ocorrer uma condição de parada. • O processamento de M para a entrada w pode parar ou ficar processando indefinidamente (ciclo ou loop infinito). Parada A parada do processamento de uma Máquina de Turing M, para a entrada w pode ser feita de duas maneiras: • Aceita a entrada w. Atinge um estado final: a máquina para, e a palavra w é aceita. Parada • Rejeita a entrada w. São duas possibilidades: ✓ A função programa é indefinida para o argumento (símbolo lido e estado corrente): a máquina para, e a palavra w é rejeitada. ✓ O argumento corrente da função programa define um movimento à esquerda, e a cabeça da fita já se encontra na célula mais à esquerda: a máquina para, e a palavra w é rejeitada. http://www.google.com/doodles/alan-turings-100th-birthday • Exemplo: Máquina de Turing: Duplo balanceamento. • Considere a linguagem L = {anbn | n 0}. • Sendo: M = ({a,b},{q0,q1,q2,q3,q4},,{q4},{A,B}, ,) • Vamos verificar como se dá o processamento para a entrada w = aabb para a Máquina de Turing M representada na máquina de estado a seguir. • Exemplo: Processamento para a entrada w = aabb. (q0,)=(q0,,D) • Exemplo: Processamento para a entrada w = aabb.. (q0,a)=(q1,A,D) • Exemplo: Processamento para a entrada w = aabb.. Logo, a entrada w = aabb é reconhecida (aceita) pela Máquina de Turing M. (q3,B)=(q3,B,D) • Exemplo: Processamento para a entrada w = aabb.. Professor Me. Paulo David pd.mnpa@gmail.com Faculdade Maurício de Nassau Curso: Sistemas de Informação Disciplina: Linguagens Formais e Autômatos Professor: Me. Paulo Roberto Sousa David Máquina de Turing
Compartilhar