Teoria da Computação e Compiladores - Ementa e Bibliografia

TEORIA DA COMPUTAÇÃO E COMPILADORES Prof MSc Renato Matroniani Máquina de Turing Análise Léxica e Sintática 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 Linguagens recursivamente enumeráveis e sensíveis ao contexto Essas linguagens estudam o que pode ser reconhecido computacionalmente Mostram que existem finitas e contáveis linguagens computáveis e infinitas e não contáveis linguagens não computáveis O que quer dizer isso Existem mais linguagens não computáveis do que computáveis Linguagens recursivamente enumeráveis e sensíveis ao contexto Através do estudo dos formalismos da máquina de Turing e das gramáticas relacionadas é desenvolvido o entendimento dessas linguagens Histórico Máquina de Turing Menezes 2011 Ciência da computação conhecimento sistematizado da computação Origem da Ciência da Computação milenar nas regiões da Mesopotâmia Egito Grécia Babilônia Índia China Roma e Asteca Início do século XX grande avanço na pesquisas para definir um modelo computacional suficientemente genérico capaz de implementar qualquer função computável para viabilizar a exploração dos limites do que pode ser computado 1936 Alan Turing traz proposta de formalismo para a representação de procedimentos efetivos Histórico Máquina de Turing Trabalho de Turing foi o primeiro a identificar programas escritos para uma máquina computacional Noções intuitivas do efetivamente computável A máquina de Turing é um formalismo muito simples universalmente conhecido e provavelmente o mais usado como modelo teórico de computação A intenção do modelo foi simular tanto quanto possível as atitudes humanas relacionadas à computação Menezes 2011 p 212 Como resultado foi criada uma fundamentação teórica para desenvolver computadores como conhecemos hoje Atualmente é considerada como uma formalização de um procedimento efetivo algoritmo ou função computável Histórico Tese de Church 1936 Alonzo Church apresenta a sua tese Tese de Church que diz que que qualquer função computável pode ser processada por uma máquina de Turing Em outras palavras existe um procedimento expresso como um algoritmo na forma de uma máquina de Turing que tem a capacidade de processar tal informação para provar a tese de Church considerase que nenhuma outra máquina ou modelo de máquina possui capacidade maior de processamento que a de Turing Dentro da Teoria da Computação então esse tese é conhecida como Hipótese de Church Histórico Máquina de Turing O trabalho de Turing foi o primeiro a identificar programas escritos para uma máquina computacional Noções intuitivas do efetivamente computável A máquina de Turing é um formalismo muito simples universalmente co nhecido e provavelmente o mais usado como modelo teórico de computação A intenção do modelo foi simular tanto quanto possível as atitudes humanas relacionadas à computação Menezes 2011 p 212 Como resultado foi criada uma fundamentação teórica para desenvolver computadores como conhecemos hoje Atualmente é considerada como uma formalização de um procedimento efetivo algoritmo ou função computável Definição Máquina de Turing Resumidamente uma máquina de Turing é um autômato cuja fita não possui tamanho máximo e pode ser usada simultaneamente como dispositivo de entrada de saída e de memória de trabalho Menezes 2011 p213 As máquinas de Turing podem aceitar linguagens recursivamente enumeráveis tipo 0 Como pela hipótese de Church a máquina de Touring é o dispositivo mais genérico entendese que as linguagens recursivamente enumeráveis represente o conjunto de todas as linguagens finitas tempo finito possíveis Definição Máquina de Turing Considere L linguagem recursivamente enumerável M máquina de Turing w palavra pertencente ou não a L M aceita L Então existe pelo menos uma palavra w que M não aceita ou não entende essa palavra processada por M gera loop infinito se w pertencer à L a máquina para e aceita L se w não pertencer à L a máquina pode parar ou entrar em loop infinito problema computável problema parcialemente solucionável Definição Máquina de Turing De acordo com Menezes 2011 p214 A máquina de Turing proposta por Alan Turing em 1936 é um mecanismo simples que formaliza a ideia de uma pessoa que realiza cálculos Lembra em muito os computadores atuais embora tenha sido proposta anos antes do primeiro computador digital Apesar de sua simplicidade o modelo máquina de Turing possui no mínimo o mesmo poder computacional de qualquer computador de propósito geral Máquina de Turing Fonte reprodução em revistagalileuglobocomTecnologianoticia201803 acesso em 02mai2021 Máquina de Turing Fonte httpswwwtecnovestecombralanturingopaidainteligenciaarticial e httpswwwufrgsbralanturingbrasil2012 acesso em 02mai2021 Máquina de Turing Fonte httpswwwufrgsbralanturingbrasil2012 acesso em 02mai2021 httpsyoutubecYw2ewoO6c4 Máquina de Turing Menezes 2011 faz um paralelo entre a Máquina de Turing e um pessoa com um instrumento de escrita e um apagador que realiza cálculos em uma folha de papel organizada em quadrados Então Inicialmente suponha que a folha de papel contém somente os dados iniciais do problema O trabalho da pessoa pode ser resumido em sequências de operações simples como segue ler um símbolo de um quadrado alterar um símbolo em um quadrado mover os olhos para outro quadrado Quando é encontrada alguma representação satisfatória para a resposta desejada a pessoa termina seus cálculos Máquina de Turing A unidade de controle possui um número finito e predefinido de estados A cabeça da fita lê o símbolo de uma célula de cada vez e grava um novo símbolo Após a leituragravação a gravação é realizada na mesma célula de leitura a cabeça move uma célula para a direita ou para a esquerda O símbolo gravado e o sentido do movimento são definidos pelo programa Máquina de Turing A função programa considera o estado corrente 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 são representados por E e D respectivamente Máquina de Turing Exemplo 1 Considere a linguagem Lanbn n0 e Máquina de Turing 𝛿 é como na tabela a seguir tal que ACEITAM L REJEITAM L e portanto LOOPM algoritmo reconhecer o primeiro símbolo a o qual é marcado como A e movimenta a cabeça da fita à direita procurar o b correspondente o qual é marcado como B repetir este ciclo sucessivamente até identificar para cada a o seu correspondente b obs o algoritmo garante que qualquer outra palavra que não esteja na forma anbn é rejeitada obs para uma determinada linguagem L sobre o alfabeto Σ L denota o seu complemento em relação ao conjunto universo Σ Máquina de Turing Exemplo 1 algoritmo reconhecer o primeiro símbolo a o qual é marcado como A e movimenta a cabeça da fita à direita procurar o b correspondente o qual é marcado como B repetir este ciclo sucessivamente até identificar para cada a o seu correspondente b obs o algoritmo garante que qualquer outra palavra que não esteja na forma anbn é rejeitada Máquina de Turing Exemplo 2 Considere a linguagem B conforme segue O algoritmo diz que M lê e continua lendo se o símbolo antes de for igual ao símbolo depois de e a cadeia é aceita se termina vazia 𝜀 ou Escrever o diagrama de estados dessa MT Máquina de Turing Máquina de Turing Exemplo 2 Esse exemplo contém descrição de alto nível pois Máquina de Turing Exemplo 2 Esse exemplo contém descrição de implementação pois