Baixe o app para aproveitar ainda mais
Prévia do material em texto
Como funciona a máquina de Como funciona a máquina de TuringTuring Máquina de Turing - A máquina de Turing possui uma memória linear infinita chamada de FITA. - Possui um formalismo reconhecedor. - A grande diferença das máquinas de Turing é que a fita não é usada apenas para a leitura, mas também para a escrita. Máquina de Turing Fita ◦ Inicialmente, recebe a palavra a ser reconhecida. ◦ Limitada à esquerda. - Representação do início da fita: $ ◦ Infinita à direita - Símbolos brancos β, após a palavra. ◦ Pode ser lida ou escrita uma posição por vez - Possui um alfabeto (símbolos terminais) ◦ Após uma operação, anda uma posição : - Para a Esquerda ou Direita Não pode ir para a esquerda se estiver em $. Máquina de Turing Fita - Cada posição da fita guarda um símbolo. - Os símbolos são lidos em sequência, um por vez pelo cabeçote. - A palavra ser reconhecida é automaticamente gravada na fita na inicialização da máquina. - Como a fita é infinita, as posições mais a direita e mais a esquerda da palavra são preenchidas com símbolos brancos ( [] ) Máquina de Turing Fita - Então se considerarmos a palavra abab como palavra de entrada na máquina, a fita deverá ficar assim. Máquina de Turing Função de transição ◦ Recebe como entrada - O estado atual - O símbolo da posição atual ◦ Resultados - O próximo estado - Símbolo a ser gravado - Direção do movimento da fita D: direita E: esquerda Máquina de Turing - A máquina de Turing realiza 3 ações por etapa 1 - Ela lê o símbolo na fita 2 - Ela reescreve o símbolo fazendo uma substituição, muitas vezes ela reescreve colocando o mesmo símbolo atual deixando a posição na fita sem efetiva alteração 3 - E move o cabeçote para a esquerda ou para a direita Máquina de Turing Cada transição tem o seguinte rótulo : Y / X, M Y = É o símbolo lido na fita. X = É o símbolo pelo qual Y deve ser substituído M = É a direção que o cabeçote deve ir (E ou D) Máquina de Turing Exemplo da máquina de Turing utilizando o alfabeto {a,b} Máquina de Turing - A palavra não precisa ser lida por inteiro para ser aceita, apenas o que importa é que a máquina pare em um estado de aceitação, seguindo o exemplo anterior, esta máquina então deveria parar no estado q1. Máquina de Turing - Mãos à obra … ou melhor … máquina à obra, vamos olhar se a palavra aab é reconhecida por esta máquina de Turing. Máquina de Turing - A máquina de Turing pode ser definifda com uma 7-tupla, usando a descrição abaixo : Máquina de Turing - Seguindo o exemplo anterior : Em memória de Alan Turing 1912-1954 Equipe : Thalia Lisboa Samuel Rodrigues Elmo Victor Slide 1 Slide 2 Slide 3 Slide 4 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14
Compartilhar