Teoria da Computação e Compiladores - Máquina de Turing

TEORIA DA COMPUTAÇÃO E COMPILADORES Prof Renato Matroniani Máquina de Touring Bibliografia Sugerida AHO A V et al Compiladores Princípios Técnicas e Ferramentas São Paulo PearsonAddisonWesley 2008 HOPCROFT J E ULLMAN J D Introdução à Teoria dos Autômatos Linguagens e Computação Rio de Janeiro Campus 2003 MENEZES P B Linguagens Formais e Autômatos Porto Alegre Sagra Luzzatto 3ª Ed 2000 178p EMENTA Gramáticas contexto Tipos de reconhecedores Operações com linguagens Propriedades das linguagens Autômatos de estados finitos Autômatos de pilha Máquina de Turing Análise léxica e sintática Tabelas de símbolos Linguagens regulares livresde Esquemas de tradução contexto e sensíveisao Ambientes de tempo de execução Linguagens intermediárias Geração e otimização de código Montadores Ligadores Projeto e implementação de um compilador fonte httpeaulasuspbrportal acesso em 18abr21 Características e propriedades da MT MT lembra em muitos aspectos o AFD e AP Além dos estados de aceitação há os estados de rejeição A fita por definição é infinita à direita Existe casos em que a fita é infinita tanto à esquerda quando à direita Para lembrar aqui na MT temos o símbolo em branco A programação da MT pode sobrescrever a cadeia string o que leva à necessidade dependendo do caso de haver um modo de guardar a informação que foi sobrescrita Uma MT é decisora se ela nunca entra em loop ou em outras palavras entra em q de aceitação ou rejeição Características e propriedades da MT Além de escrever sobre a fita a MT pode ler a partir dela Os estados especiais para rejeitar e aceitar fazem efeito imediatamente A MT pode não parar para determinadas cadeias pois neste caso a cadeia não pertence à linguagem reconhecida pela máquina Características e propriedades da MT A máquina de Turing é um dispositivo de reconhecimento de linguagens irrestritas Um modelo que permite o estudo da computabilidade ou seja tudo que é computável por uma MT também é computável por um computador moderno O inverso também é válido Características e propriedades da MT Formalização matemática da MT Funcionamento da Máquina de Turing No início temos a entrada mais à esquerda da fita O símbolo em branco é considerado o fim da entrada A máquina começa apontando para a primeira posição da fita A MT faz a leitura muda de estados e gera uma informação dependendo de 𝛿 A MT para somente em um estado de aceitação ou rejeição Além dessas duas opções ele pode nunca parar loop infinito Funcionamento da Máquina de Turing Considerar três variáveis estado atual da MT conteúdo da fita posição da cabeça de fita Funcionamento da Máquina de Turing Notação simplificada para o exemplo estado atual da MT 0 conteúdo da fita 101101111 posição da cabeça de fita 1011q701111 Funcionamento da MT Exemplo Escreva a função de transição de estado na forma e explique 𝛿𝑞i 𝑞j 𝐷 𝑜𝑢 𝐸 para as seguintes situações considerando a palavra 𝑢𝑎𝑐𝑣 e os estados 𝑞i e 𝑞j a 𝑢𝑎𝒒𝒊𝑏𝑣 origina 𝑢𝒒𝒋𝑎𝑐𝑣 b 𝑢𝑎𝒒𝒊𝑏𝑣 origina 𝑢𝑎𝑏𝒒𝒋𝑐 Funcionamento da Máquina de Turing Configuração inicial q0w Configuração de aceitação estado atual qaceita Configuração de rejeição estado atual qrejeita Para a MT aceitar uma entrada w com diversas configurações de C1 a Ck se a C1 é a configuração inicial da MT da entrada w1 b para cada C1 temos a geração de Ci1 c Ck é a configuração de aceitação como pederíamos explicar isso em outras palavras Variantes da Máquina de Turing a MT é um modelo robusto que possui variações que podem reconhecer a mesma classe de linguagens Máquina de Turing multifita Máquina de Turing com fita ilimitada em ambos os lados Máquina de Turing não determinísticas Máquina de Turing multifitas k fitas cada fita possui sua própria cabeça de leitura e de escrita no início do processo computacional a cadeia de entrada fica na primeira fita e as demais fitas com branco cada fita possui sua própria cabeça que move independentemente uma da outra Toda máquina de Turing multifita possui uma MT de uma única fita que lhe é equivalente Máquina de Turing multifitas k3 fitas Máquina de Turing multifitas MT com fita única equivalente S single Máquina de Turing multifitas leitura de uma MT multifita leitura dos símbolos atuais percorrer a fita com pontos em cima até o k1ésimo atualização das cabeças percorre a fita fazendo as atualizações conforme a função de transição tira e coloca pontos até o k1ésimo MT com fitas ilimitadas E e D Como provar a segunda figura a partir da primeira para provar usar e reparar na movimentação D e E além do símbolo para indicar o início da fita MT não determinísticas não determinística envolve probabilidades Desafio Exemplo 2 Considere uma MT M2 descrita conforme segue M2 decide 𝐴 02𝑛 𝑛 0 onde A é uma linguagem de 0s onde o comprimento é uma potencia de 2 Matematicamente um número obtido de um cálculo de potência de 2 sempre que eu dividilo por 2 terei um número par ou o valor 1 Considere também o programa escrito em linguagem intermediária a seguir sobre a cadeia de entrada w a Varra da E para a D na fita marcando um 0 não e outro sim bSe em q1 a fita continha um único 0 aceite c Se em q1 a fita continha mais que um único 0 e esse número for ímpar rejeite d Retorne a cabeça de leitura para o extremo esquerdo da fita e Vá para q1