Cap_09.pdf

Linguagens Formais e Autômatos

Paulo Blauth Menezes

Linguagens Formais e Autômatos 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 de Linguagens e Conclusões


9 - Hierarquia de Classes de Linguagens e Conclusões

9.1 Hierarquia de Chomsky

9.2 Conclusões

9.3 Leitura Complementar: Gramática de Grafos




9.1 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


Figura 1.

Linguagens Regulares ouTipo 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 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


Exemplos de problemas que não podem ser 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, sequências de operações, etc.

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


De qualquer forma, o estudo das Linguagens Livres do Contexto tem sido de especial interesse

permite 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ão solucioná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


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




9.2 Conclusões



9.2 Conclusões Linguagens Formais oferecem meios para modelar e

desenvolver ferramentas que

especificam linguagens

processos de análise

propriedades

limitações algorítmicas


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 n-dimensionais, ênfase bi/tridimensionais 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 e/ou

comunicantes): especificação formal e prova de propriedades


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


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




9.2 Conclusões



9.3 Leitura Complementar: Gramática de Grafos Uma abordagem às linguagens n-dimensionais

Ideia 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


Gramáticas de grafos

caso particular das gramáticas categoriais

nenhum conceito de Teoria das Categorias é formalmente introduzido aqui


Gramáticas categoriais podem ser definidas sobre

palavras grafos conjuntos parcialmente ordenados redes autômatos máquinas linguagens de programação etc., desde que sejam satisfeitas determinadas condições

Adicionalmente, as derivações são generalizadas


¾

¾ 2

Exp: Gramática de Grafos: PacMan Jogo PacMan (simplificado)

tabuleiro PacMan conjunto de fantasmas conjunto de maçãs


“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)


Regras de produção:

¾¾

move:

come:

mata:


Grafo resultante da aplicação da regra move:

¾

2¾


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


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)


Exercício: Jogo de Damas

jogador com as pedras brancas inicia o jogo

Dica na definição da regra “comer uma pedra”, lembre-se de que o

movimento é sempre em “linha reta” não pode fazer uma “curva” de 90

o no tabuleiro



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 de Linguagens e Conclusões



[email protected] Departamento de Informática Teórica

Instituto de Informática / UFRGS

Documents

Cap_09.pdf