Teoria da Computação e Compiladores: Conceitos e Aplicações de Linguagens em Autômatos

TEORIA DA COMPUTAÇÃO E COMPILADORES Engenharia da Computação Prof MSc Renato Matroniani Aplicação das linguagens em autômatos Relacionar o conceito de linguagens regulares e LLC com autômatos Bibliografia Sugerida MENEZES P B Linguagens Formais e Autômatos Porto Alegre Sagra Luzzatto 3ª Ed 2000 178p EMENTA Gramáticas Linguagens regulares livres decontexto e sensíveisao 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 Esquemas de tradução 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 Entendimento computacional de reconhecimento de padrões reconhecimento do genoma reconhecimento de gênero musical sistemas de reconhecimento de voz automação residencial detecção de defeitos biológicos em imagens reconhecimento e busca de rostos imagens Entendimento computacional de reconhecimento de padrões fonte hpeaulasuspbrportal acesso em 18abr21 Entendimento computacional de reconhecimento de padrões fonte hpeaulasuspbrportal acesso em 18abr21 Hierarquia de Chomsky e Gramáticas regras de gramática semelhanteàs do português representam um conjunto de sequências Como faríamos uma árvore de derivação de uma frase em português Autômatos eou Máquina de Turing são reconhecedores ou seja reconhecem ou não se uma dada cadeia pertencem à uma determinadalinguagem O reconhecimento de uma cadeira w pertence a uma G é chamado de análise sintática veremos mais adiante Revendo gramática regular fonte hpeaulasuspbrportal acesso em 18abr21 Revendo gramática regular fonte hpeaulasuspbrportal acesso em 18abr21 Revendo gramática regular fonte hpeaulasuspbrportal acesso em 18abr21 Linguagens livres do contexto formalismos Gramática livre de contexto é uma gramática com regras de produção porém mais livres que na gramática regular Autômato com pilha é um formalismo que adiciona ao autômato finito uma memória auxiliar do tipo pilha Essa memória auxiliar pode ser lida ou gravada Linguagens livres do contexto Definição de Gramática Livre do Contexto Uma gramática livre do contexto 𝐺 é uma gramática 𝐺 𝑉 𝑇 𝑃 𝑆 com a restrição de que qualquer regra de produção de P é da forma 𝐴 𝛼 onde 𝐴 é uma variável de 𝑉 e 𝛼 uma palavra de 𝑉 𝑇 Portanto uma gramática livre do contexto é uma gramática na qual o lado esquerdo das produções contém exatamente uma variável Na prática Linguagens livresdecontexto Tipo 2 Esse é um caso clássico e de fundamental importância no estudo da computação e informática Permite estabelecer analogia com estruturas de duplo balanceamento em linguagens de programação como Pascal C Java etc Por exemplo Gramáticas livres do contexto Árvore de derivação em compiladores e processadores de texto a derivação é representada da seguinte forma Gramáticas livres do contexto EXEMPLO Como é representada a árvore de derivação da operação 𝒙 𝒙 𝒙 Linguagens livresdecontexto Outras formas de representação de 𝑥 𝑥 𝑥 𝐸 𝐸 𝐸 𝑥 𝐸 𝑥 𝐸 𝐸 𝑥 𝑥 𝐸 𝑥 𝑥 𝑥 𝐸 𝐸 𝐸 𝐸 𝐸 𝐸 𝐸 𝐸 𝑥 𝐸 𝑥 𝑥 𝑥 𝑥 𝑥 𝐸 𝐸 𝐸 𝐸 𝐸 𝐸 𝑥 𝐸 𝐸 𝑥 𝑥 𝐸 𝑥 𝑥 𝑥 𝑒𝑡𝑐 Observação no item a em cada passo de derivação sempre é derivada a variável mais à esquerda Analogamente para a variável mais a direita no item b Linguagens livresdecontexto Exemplo Suponha uma linguagem livre de contexto L1 anb2n n1 que é gerada pela gramática livre de contexto E1 à aE1bb abb Pela lógica qual a Gramática E2 gerada pela linguagem L2 a2nbn n1 Autômatos com pilha Assim como as linguagens livres Tipo 1 as linguagens livres do contexto Tipo 2 podem ser associadas a um formalismo do tipo autômato denominado autômato com pilha De acordo com Menezes 2011 O autômato com pilha é análogo ao autômato finito incluindo uma pilha como memória auxiliar e a facilidade de não determinismo A pilha é independente da fita de entrada e não possui limite máximo de tamanho o que implica uma noção de tão grande quanto se queira Portanto é baseada na noção de conjunto infinitamente contável Estruturalmente sua principal característica é que o último símbolo gravado é o primeiro a ser lido A base de uma pilha é fixa e define o seu início O topo é variável e define a posição do último símbolo gravado Autômatos com pilha Fonte MENEZES P B Linguagens Formais e Autômatos 2011 p 175 fonte hpeaulasuspbrportal acesso em 18abr21 Na prática de um autômato fonte hpeaulasuspbrportal acesso em 18abr21 Autômatos com pilha Definições de automatos a pilha 1 O valor inicial da pilha é vazio e o autômato para aceitando ao atingir um estado final 2 a pilha contém inicialmente um símbolo especial denominado símbolo inicial da pilha Não existem estados finais e o autômato para aceitando quando a pilha estiver vazia Essas duas definições possuem o mesmo sentido computacional Partes de um automato a pilha não deteminístico Fita Análoga à do autômato finito Pilha Memória auxiliar do tipo pilha que pode ser usada para leitura e gravação Unidade de controle Reflete o estado corrente da máquina Possui uma cabeça de fita e uma cabeça de pilha Programa função programa ou função de transição Comanda a leitura da fita leitura e gravação da pilha e define o estado da máquina Outra definição para um automato a pilha Um autômato com pilha não determinístico ou simplesmente autômato com pilha frequentemente abreviado por AP M é uma 6upla 𝑀 Σ 𝑄 𝛿 𝑞0 𝐹 𝑉 onde Σ é um alfabeto de símbolos de entrada ou simplesmente alfabeto de entrada Q é um conjunto de estados possíveis do autômato o qual é finito δ é uma função programa ou simplesmente programa ou ainda função de transição suponha que ε e não são símbolos do alfabeto de entrada δ Q Σ ε V ε 2QV a qual é uma função total Autômato a pilha Representando graficamente Exemplos de operações com Autômato a pilha Linguagem aceita linguagem rejeitada linguagem loop Seja M Σ Q δ q0 F V um autômato com pilha Então A linguagem aceita ou linguagem reconhecida por M denotada por ACEITAM ou LM é o conjunto de todas as palavras pertencentes a Σ aceitas por M a partir do estado inicial q0 A linguagem rejeitada por M denotada por REJEITAM é o conjunto de todas as palavras pertencentes a Σ rejeitadas por M a partir do estado inicial q0 A linguagem loop de M denotada por LOOPM é o conjunto de todas as palavras pertencentes a Σ para as quais M fica processando indefinidamente a partir do estado inicial q0 Exemplo Autômato a pilha Considere o seguinte autômato com pilha M1 a b q0 q1 qf δ1 q0 qf B no qual δ1 é como a seguir é tal que ACEITAM1 L1 δ1 q0aεq0B δ1 q0bBq1ε δ1 q0qfε δ1 q1bBq1ε δ1 q1qfε Construa o diagrama do autômato com base nas informações Exemplo Autômato a pilha No estado q0 para cada símbolo a lido da fita é armazenado um símbolo B na pilha No estado q1 é realizado um batimento verificando se para cada símbolo b da fita existe um correspondente B na pilha O algoritmo somente aceita se ao terminar de ler toda a palavra de entrada a pilha estiver vazia δ1 q0aεq0B δ1 q0bBq1ε δ1 q0qfε δ1 q1bBq1ε δ1 q1qfε Exemplo 2 Autômato a pilha Autômato com pilha anbmanm Considere a seguinte linguagem sobre o alfabeto a b L4 anbmanm n 0 m 0 O autômato não determinístico M4 é tal que ACEITAM4 L4 M4 empilha um símbolo auxiliar X para cada a ou b em q0 ou q1 respectivamente Após em q2 verifica se o número de a no sufixo é igual ao de X empilhado Construa o diagrama do autômato que segue este programa Exemplo Exercícios para nota 1º Bimestre 7 Quais das seguintes palavras são aceitas pelos autômatos finitos não determinís9cos sobre o alfabeto Σ a b ilustrado na figura a seguir bb bab bbbaaa bbbbbbababababa Exemplo Exercícios para nota 8 Quais das seguintes palavras são aceitas pelos autômatos finitos não determinís9cos sobre o alfabeto Σ a b ilustrado na figura a seguir bb bab bbbaaa bbbbbbababababa Exemplos fonte hpeaulasuspbrportal acesso em 18abr21 Exemplos fonte hpeaulasuspbrportal acesso em 18abr21 fonte hpeaulasuspbrportal acesso em 18abr21 Exemplos fonte hpeaulasuspbrportal acesso em 18abr21 Exemplos fonte hpeaulasuspbrportal acesso em 18abr21 Exemplos Sequências diferentes das iniciadas com a e c não são lidas pelo autômato Por que