Linguagens Formais e Autômatos - Hierarquia de Chomsky

Linguagens Formais e Autômatos P Blauth Menezes 1 Linguagens Formais e Autômatos P Blauth Menezes blauthinfufrgsbr Departamento de Informática Teórica Instituto de Informática UFRGS Linguagens Formais e Autômatos P Blauth Menezes 2 Linguagens Formais e Autômatos P Blauth Menezes 1 Introdução e Conceitos Básicos 2 Linguagens e Gramáticas 3 Linguagens Regulares 4 Propriedades das Linguagens Regulares 5 Autômato Finito com Saída 6 Linguagens Livres do Contexto 7 Propriedades e Reconhecimento das Linguagens Livres do Contexto 8 Linguagens Recursivamente Enumeráveis e Sensíveis ao Contexto 9 Hierarquia de Classes e Linguagens e Conclusões Linguagens Formais e Autômatos P Blauth Menezes 3 9 Hierarquia de Classes de Linguagens e Conclusões 91 Hierarquia de Chomsky 92 Conclusões 93 Leitura Complementar Gramática de Grafos Linguagens Formais e Autômatos P Blauth Menezes 4 9 Hierarquia de Classes de Linguagens e Conclusões Linguagens Formais e Autômatos P Blauth Menezes 5 9 Hierarquia de Classes de Linguagens e Conclusões 91 Hierarquia de Chomsky Constituída pelas classes inclusões próprias Regulares ou Tipo 3 Livres do Contexto ou Tipo 2 Sensíveis ao Contexto ou Tipo 1 Recursivamente Enumeráveis ou Tipo 0 Linguagens Formais e Autômatos P Blauth Menezes 6 Linguagens Regulares ou Tipo 3 Linguagens Recursivamente Enumeráveis ou Tipo 0 Linguagens Livres do Contexto ou Tipo 2 Linguagens Sensíveis ao Contexto ou Tipo 1 Noam Chomsky definiu estas classes como potenciais modelos para linguagens naturais Linguagens Formais e Autômatos P Blauth Menezes 7 Linguagens de programação nem sempre são tratadas adequadamente na Hierarquia de Chomsky Existem linguagens que não são livres do contexto para as quais poder dos formalismos sensíveis ao contexto é excessivo inadequados principalmente no que se refere à complexidade Conhecimento das linguagens sensíveis ao contexto relativamente limitado dificulta o seu tratamento Linguagens Formais e Autômatos P Blauth Menezes 8 Exemplos de problemas que não Livres do Contexto múltiplas ocorrências de um mesmo trecho de programa como a declaração de um identificador e suas referências de uso análogo a wcw w é palavra de a b alguns casos de validação de expressões com variáveis de tipos diferentes associação de um significado semântica de um trecho de programa análise de um conjunto de informações dependentes de contextos como identificadores ambientes tipos de dados localização seqüências de operações etc Linguagens Formais e Autômatos P Blauth Menezes 9 Para algumas linguagens de programação Classe das Linguagens Livres do Contexto é excessiva Classe das Linguagens Regulares insuficiente Linguagem Livre do Contexto Determinística pode ser denotada por um Autômato com Pilha Determinístico é possível implementar facilmente um reconhecedor com tempo de processamento proporcional a 2n n é o tamanho da entrada muito mais eficiente que o melhor algoritmo conhecido para as linguagens livres do contexto Linguagens Formais e Autômatos P Blauth Menezes 10 De qualquer forma o estudo das Linguagens Livres do Contexto tem sido de especial interesse permitem uma representação simples da sintaxe adequada para estruturação formal e para análise computacional Entretanto o estudo das Linguagens Livres do Contexto tem mostrado problemas nãosolucionáveis determinar se uma gramática é ambígua existem duas ou mais árvores de derivação distintas para uma mesma palavra não existe um algoritmo que verifique a igualdade de duas linguagens dificulta otimização e teste de processadores de linguagens Linguagens Formais e Autômatos P Blauth Menezes 11 Portanto dependendo da linguagem e dos objetivos do trabalho estudos específicos eventualmente fora da Hierarquia de Chomsky são recomendados ou necessários exemplo apresentado Classe de Linguagens Recursivas Linguagens Formais e Autômatos P Blauth Menezes 12 9 Hierarquia de Classes de Linguagens e Conclusões 91 Hierarquia de Chomsky 92 Conclusões 93 Leitura Complementar Gramática de Grafos Linguagens Formais e Autômatos P Blauth Menezes 13 92 Conclusões Linguagens Formais oferecem meios para modelar e desenvolver ferramentas que especificam linguagens processos de análise propriedades limitações algorítmicas Linguagens Formais e Autômatos P Blauth Menezes 14 Alguns problemas possuem questões em aberto tradução de linguagens com ênfase nas naturais explosão de estados dos autômatos finitos desenvolvimento de soluções possivelmente complexas exige um número excessivo de estados importante tema de pesquisa tratamento de linguagens ndimensionais ênfase bitridimensionais imagens animações sistemas biológicos simulação do desenvolvimento de sistemas vivos tanto no plano quanto no espaço sistemas concorrentes eventualmente distribuídos eou comunicantes especificação formal e prova de propriedades Linguagens Formais e Autômatos P Blauth Menezes 15 Limitação do trabalho desenvolvido formalismos desenvolvidos não são adequados para o tratamento de problemas complexos não possuem construções composicionais em suas definições sem qualquer estruturação modular ou hierárquica Algumas construções composicionais foram exploradas união intersecção complemento etc limitadas em termos de expressividade Linguagens Formais e Autômatos P Blauth Menezes 16 Construções composicionais mais ricas inspiradas em Teoria das Categorias constituem uma álgebra sobre os formalismos com operações expressivas desenvolvimento de soluções complexas de forma simples em grande parte dos casos corretas por construção abordagem transcende o objetivo da disciplina importante linha de pesquisa para quem deseja dar continuidade aos estudos Linguagens Formais e Autômatos P Blauth Menezes 17 9 Hierarquia de Classes de Linguagens e Conclusões 91 Hierarquia de Chomsky 92 Conclusões 93 Leitura Complementar Gramática de Grafos Linguagens Formais e Autômatos P Blauth Menezes 18 93 Leitura Complementar Gramática de Grafos Uma abordagem às linguagens ndimensionais Idéia básica das gramáticas de grafos análoga à das Gramáticas de Chomsky Gramática de Grafos regras de produção pares mas de grafos derivação substituição de um subgrafo de acordo com uma regra de produção Linguagens Formais e Autômatos P Blauth Menezes 19 Gramáticas de grafos caso particular das gramáticas categoriais nenhum conceito de Teoria das Categorias é formalmente introduzido Linguagens Formais e Autômatos P Blauth Menezes 20 Gramáticas categoriais podem ser definidas sobre palavras grafos conjuntos parcialmente ordenados redes autômatos máquinas linguagens de programação desde que sejam satisfeitas determinadas condições Adicionalmente as derivações são generalizadas Linguagens Formais e Autômatos P Blauth Menezes 21 Exp Gramática de Grafos PacMan Jogo PacMan simplificado tabuleiro PacMan conjunto de fantasmas conjunto de maçãs 2 Linguagens Formais e Autômatos P Blauth Menezes 22 Palavra da linguagem nodos pretos lugares do tabuleiro arestas caminhos possíveis entre dois lugares PacMan fantasmas e maçãs nodos com simbologia própria arcos denotam o posicionamento no tabuleiro nodo branco maçã já comida fase em que se encontra o jogo no caso segunda fase Linguagens Formais e Autômatos P Blauth Menezes 23 Regras de produção move come mata Linguagens Formais e Autômatos P Blauth Menezes 24 Grafo resultante da aplicação da regra move 2 Linguagens Formais e Autômatos P Blauth Menezes 25 Comparativamente com as gramáticas de Chomsky em geral não distinguem entre variáveis e terminais todos os símbolos grafos são tratados como terminais possui símbolo inicial grafo inicial linguagem gerada conjunto de grafos que podem ser gerados via derivações a partir do grafo inicial Linguagens Formais e Autômatos P Blauth Menezes 26 Exercício Jogo da Velha jogadas alternadas de dois jogadores condição de parada quando um dos jogadores completa uma linha de três casas horizontal vertical ou oblíqua Linguagens Formais e Autômatos P Blauth Menezes 27 Exercício Jogo de Damas jogador com as pedras brancas inicia o jogo Dica na definição da regra comer uma pedra lembrese de que o movimento é sempre em linha reta não pode fazer uma curva de 90 o no tabuleiro Linguagens Formais e Autômatos P Blauth Menezes 28 Linguagens Formais e Autômatos P Blauth Menezes 1 Introdução e Conceitos Básicos 2 Linguagens e Gramáticas 3 Linguagens Regulares 4 Propriedades das Linguagens Regulares 5 Autômato Finito com Saída 6 Linguagens Livres do Contexto 7 Propriedades e Reconhecimento das Linguagens Livres do Contexto 8 Linguagens Recursivamente Enumeráveis e Sensíveis ao Contexto 9 Hierarquia de Classes e Linguagens e Conclusões Linguagens Formais e Autômatos P Blauth Menezes 29 Linguagens Formais e Autômatos P Blauth Menezes blauthinfufrgsbr Departamento de Informática Teórica Instituto de Informática UFRGS