Baixe o app para aproveitar ainda mais
Prévia do material em texto
04/05/2012 1 LINGUAGENS LIVRES DO CONTEXTO INTRODUÇÃO À TEORIA DA COMPUTAÇÃO 1 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagem Livre do Contexto � Hierarquia de Chomsky é a classificação hierárquica de linguagens 2 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Fonte: (Menezes,1999) Linguagem Livre do Contexto � Correspondência entre as classes de linguagens, gramáticas e reconhecedores 3 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagem Gramática Reconhecedor Tipo 0: enumerável recursivamente irrestrita máquinas de Turing Tipo 1: sensível ao contexto sensível ao contexto autômato limitado linearmente Tipo 2: livre do contexto livre do contexto autômatos com pilha Tipo 3: regular regular autômatos finitos Linguagem Livre do Contexto � A Classe das Linguagens Livres do Contexto ou Tipo 2 contém propriamente a Classe das Linguagens Regulares. � Seu estudo é de fundamental importância na informática pois: � Compreende um universo mais amplo de linguagens (comparando-se com as regulares) � Trata questões como parênteses balanceados, construções bloco-estruturadas, entre outras, típicas de linguagens de programação como Pascal, C, Algol, etc. 4 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagem Livre do Contexto � Seu estudo é de fundamental importância na informática pois: � Os algoritmos reconhecedores e geradores que implementam as Linguagens Livres do Contexto são relativamente simples e possuem uma boa eficiência; � Exemplos típicos de aplicações dos conceitos e resultados referentes às Linguagens Livres do Contexto são analisadores sintáticos, tradutores de linguagens e processadores de texto em geral 5 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagens Livres do Contexto � O estudo das Linguagens Livres do Contexto ou Tipo 2, pode ser abordado através de formalismos: � Operacional ou reconhecedor (máquina): � Autômato com Pilha: autômato cuja estrutura básica é análoga à do Autômato Finito, adicionando uma memória auxiliar tipo pilha (a qual pode ser lida ou gravada) e a facilidade de não-determinismo � Axiomático ou gerador (gramática): � Gramática Livre do Contexto: gramática onde as regras de produção são definidas de forma mais livre que na Gramática Regular 6 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 04/05/2012 2 Gramática Livre do Contexto � Uma Gramática Livre do Contexto (GLC) é uma gramática G = ( V, T, P, S ) � Qualquer regra de produção de P é da forma A → α onde A é uma variável de V e α uma palavra de (V ∪ T)* � Uma GLC é uma gramática onde o lado esquerdo das produções contém exatamente uma variável � Uma linguagem é dita Linguagem Livre do Contexto (LLC) ou Tipo 2 se for gerada por uma Gramática Livre do Contexto 7 Profa. Ellen Souza - https://sites.google.com/site/ellenuast O nome “Livre do Contexto” � Deve-se ao fato de representar a mais geral classe de linguagens cuja produção é da forma A → α � Ou seja, em uma derivação, a variável A deriva α sem depender ("Livre") de qualquer análise dos símbolos que antecedem ou sucedem A ("Contexto") na palavra que está sendo derivada � Assim toda Linguagem Regular é Livre do Contexto 8 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Relembrando Gramática Regular � Uma Gramática Regular contém as seguintes regras de produção � A � w B ou A � w - Gramática Linear à Direita (GLD) � | w | ≤ 1 - Gramática Linear Unitária à Direita (GLUD) � A � B w ou A � w - Gramática Linear à Esquerda (GLE) � | w | ≤ 1 Gramática Linear Unitária à Esquerda (GLUE) � Exemplos: � Seja G = ({S}, {x, y}, P, S ), e P = { S → xyS, S → x} � Seja G = ({S1, S2, S3}, {a, b}, P, S1 ) e P = { S1 → S2ab, S2 → S2ab | S3, S3 → a} � Seja G = ({S, A, B}, {a, b}, P, S ) e P = { S → A, A → aB | λ, B → Ab} 9 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagem Livre do Contexto � Exemplo 1: LLC Duplo Balanceamento � Considere a linguagem: L1 = { an bn | n ≥ 0 } � A seguinte Gramática Livre do Contexto: G1 = ({ S }, { a, b }, P1, S), onde: P1 = {S → aSb | S → ε}, é tal que GERA(G1) = L1 � Derivação da palavra aabb: � Derivação Regra de Produção � S ⇒ aSb (S → aSb) � ⇒ aaSbb (S → aSb) � ⇒ aa ε bb (S → ε) � ⇒ aabb 10 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagem Livre do Contexto � Exemplo 1: LLC Duplo Balanceamento � Considere a linguagem: L1 = { an bn | n ≥ 0 } � A seguinte Gramática Livre do Contexto: G1 = ({ S }, { a, b }, P1, S), onde: P1 = {S → aSb | S → ε}, é tal que GERA(G1) = L1 � Esta linguagem é um exemplo clássico e de fundamental importância no estudo das Linguagens Livres do Contexto, pois permite estabelecer analogia entre anbn e linguagens que possuem duplo balanceamento como, por exemplo: � Linguagens bloco-estruturadas do tipo BEGIN END, { } � Linguagens com parênteses balanceados na forma ( ) 11 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Linguagem Livre do Contexto � Exemplo 2: LLC Expressões Aritméticas � A linguagem L2 gerada por G2 é composta de expressões aritméticas contendo colchetes balanceados, dois operadores e um operando: � G2 = ({ E }, { +, *, [,], x }, P2, E), onde: P2 = {E →E+E | E*E | [E] | x } � Derivação da expressão [x+x]*x � Derivação Regra de Produção � E ⇒ E*E (E → E*E ) � ⇒ [E]*E (E → [E]) � ⇒ [E+E]*E (E →E+E) � ⇒ [x+E]*E (E → x) � ⇒ [x+x]*E (E → x) � ⇒ [x+x]*x (E → x) 12 Profa. Ellen Souza - https://sites.google.com/site/ellenuast É possível gerar a mesma expressão com outra seqüência de derivação? Quantas seqüências distintas são possíveis? 04/05/2012 3 Árvore de Derivação � Em algumas aplicações como compiladores e processadores de textos, freqüentemente é conveniente representar a derivação de palavras na forma de árvore, partindo do símbolo inicial como a raiz, e terminando em folhas de terminais 13 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Árvore de Derivação � Para uma determinada Gramática Livre do Contexto, a representação da derivação de palavras na forma de árvore, denominada Árvore de Derivação, é como: 14 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Árvore de Derivação � A raiz é o símbolo inicial da gramática � Os vértices interiores obrigatoriamente são variáveis. Se A é um vértice interior e X1, X2, ...,Xn são os filhos de A, então A → X1X2...Xn é uma produção da gramática e os vértices X1, X2, ...,Xn estão ordenados da esquerda para a direita � Um vértice folha é um símbolo terminal, ou o símbolo vazio 15 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Árvore de Derivação � Exemplo 3: Árvore Duplo Balanceamento para e palavra aabb � Considere a linguagem: L1 = { an bn | n ≥ 0 } � A seguinte Gramática Livre do Contexto: G1 = ({ S }, { a, b }, P1, S), onde: � P1 = {S → aSb | S → ε}, é tal que GERA(G1) = L1 16 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Árvore de Derivação � Exemplo 4: Expressões Aritméticas para a palavra [x+x]*x � A linguagem L2 gerada por G2 é composta de expressões aritméticas contendo colchetes balanceados, dois operadores e um operando: � G2 = ({ E }, { +, *, [,], x }, P2, E), onde: � P2 = {E →E+E | E*E | [E] | x } 17 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Árvore de Derivação � Uma única árvore de derivação pode representar derivações distintas de uma mesma palavra. � A palavra x+x*x pode ser gerada por diversas derivações: a) E ⇒E+E ⇒ x+E ⇒ x+E*E ⇒ x+x*E ⇒ x+x*x b) E ⇒ E+E ⇒ E+E*E ⇒ E+E*x ⇒ E+x*x ⇒ x+x*x c) E ⇒ E+E ⇒ E+E*E ⇒ x+E*E ⇒ x+x*E⇒ x+x*x d) etc 18 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 04/05/2012 4 Árvore de Derivação � A Derivação mais à Esquerda de uma árvore de derivação é a seqüência de produção aplicada sempre à variável mais à esquerda � A Derivação mais à Direita de uma árvore de derivação é a seqüência de produção aplicada sempre à variável mais à direita 19 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Ambigüidade � Eventualmente, uma mesma palavra pode ser associada a duas ou mais árvores de derivação, determinando uma ambigüidade � Nem sempre é possível eliminar ambigüidades. � É fácil definir linguagens para as quais qualquer Gramática Livre do Contexto é ambígua � Uma Gramática Livre do Contexto é dita uma Gramática Ambígua, se existe uma palavra que possua duas ou mais árvores de derivação. 20 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Ambigüidade � Exemplo 5: Gramática Ambígua � Gerar a árvore de derivação da palavra x+x*x � A expressão x+x*x pode ser gerada por árvores distintas. Portanto, a gramática em questão é ambígua 21 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Ambigüidade � Uma linguagem é uma Linguagem Inerentemente Ambígua se qualquer Gramática Livre do Contexto que a define é ambígua � Uma linguagem é uma Linguagem Não Ambígua se existir uma Gramática Livre do Contexto não ambígua, que a define 22 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Ambigüidade � G1 = ({S}, {a, +}, S, P1), tal que P1={S → a | S + S} � Gerar a cadeia a + a � S → S + S → S + a → a + a (derivação à direita) � S → S + S → a + S → a + a (derivação à esquerda) � G2 = ({S}, {a, +}, S, P1), tal que P2={S → a | a + S} � Gerar a cadeia a + a � S → a + S → a + a � G3 = ({S}, {a, +}, S, P1), tal que P3={S → a | a + a | S + S} � Gerar a cadeia a + a � S → S + S → S + a → a + a (derivação à direita) � S → S + S → a + S → a + a (derivação à esquerda) 23 Profa. Ellen Souza - https://sites.google.com/site/ellenuast G2 é não ambígua G1 é ambígua G3 é ambígua Contudo, a linguagem L = L(G1) = L(G2) = L(G3), é não ambígua uma vez que existe um gramática (G2)que é não ambígua Simplificação de Gramáticas Livres do Contexto � É possível simplificar alguns tipos de produções sem reduzir o poder de geração das Gramáticas Livres do Contexto � Em geral, as simplificações de gramáticas são usadas na construção e otimização de algoritmos e na demonstração de teoremas. 24 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 04/05/2012 5 Simplificação de Gramáticas Livres do Contexto � As seguintes simplificações são apresentadas: 1. Exclusão de variáveis ou terminais não-usados para gerar palavras 2. Exclusão de produções vazias da forma A → ε � Se a palavra vazia pertence à linguagem, é incluída uma produção vazia específica para tal fim 3. Exclusão de produções da forma A →B, � Produções que simplesmente substituem uma variável por outra e, conseqüentemente, não adicionam qualquer informação de geração de palavras 25 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Autômato com Pilha � Analogamente às Linguagens Regulares, a Classe das Linguagens Livres do Contexto pode ser associada a um formalismo do tipo autômato, denominado Autômato com Pilha � 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 26 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Autômato com Pilha � A pilha é independente da fita de entrada e não possui limite máximo de tamanho ("infinita"). � Estruturalmente, sua principal característica é que o último símbolo gravado é o primeiro a ser lido 27 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 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ômato com Pilha � Qualquer Linguagem Livre do Contexto pode ser reconhecida por um Autômato com Pilha com somente um estado (ou três estados, dependendo da definição). � A estrutura de pilha é suficiente como única memória, não sendo necessário usar os estados para "memorizar" informações passadas � A estrutura de estados no Autômato com Pilha poderia ser excluída sem reduzir o poder computacional 28 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Autômato com Pilha � O modelo Autômato com Pilha possui duas definições universalmente aceitas que diferem no critério de parada do autômato: � O valor inicial da pilha é vazio e o autômato pára aceitando ao atingir um estado final; � A pilha contém, inicialmente, um símbolo especial denominado símbolo inicial da pilha. Não existem estados finais e o autômato pára aceitando quando a pilha estiver vazia � As duas definições são equivalentes, sendo fácil modificar um Autômato com Pilha para satisfazer a outra definição 29 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Autômato com Pilha � Um Autômato com Pilha ou Autômato com Pilha Não- Determinístico é composto, basicamente, por quatro partes: � Fita. Análoga à do Autômato Finito; � Pilha. Memória auxiliar que pode ser usada livremente 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 ou Função de Transição. Comanda a leitura da fita, leitura e gravação da pilha e define o estado da máquina. 30 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 04/05/2012 6 Autômato com Pilha � A pilha é dividida em células, armazenando, cada uma, um símbolo do alfabeto auxiliar � O alfabeto auxiliar pode ser igual ao alfabeto de entrada � Em uma estrutura do tipo pilha, a leitura ou gravação é sempre na mesma extremidade, denominada topo � Não possui tamanho fixo e nem máximo, sendo seu tamanho corrente igual ao tamanho da palavra armazenada. � Seu valor inicial é vazio 31 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Autômato com Pilha � A unidade de controle possui um número finito e predefinido de estados. Possui uma cabeça de fita e uma cabeça de pilha: � Cabeça da Fita. � Unidade de leitura a qual acessa uma célula da fita de cada vez � Movimenta-se exclusivamente para a direita. � É possível testar se a entrada foi completamente lida; 32 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Autômato com Pilha � Cabeça da Pilha. � Unidade de leitura e gravação a qual move para a esquerda (ou "para cima") ao gravar e para a direita (ou "para baixo") ao ler um símbolo. � Acessa um símbolo de cada vez, estando sempre posicionada no topo. � A leitura exclui o símbolo lido. � É possível testar se a pilha está vazia. � Em uma mesma operação de gravação, é possível armazenar uma palavra composta por mais de um símbolo. Neste caso, o símbolo do topo é o mais à esquerda da palavra gravada 33 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Autômato com Pilha � O programa é uma função parcial que, dependendo do estado corrente, símbolo lido da fita e símbolo lido da pilha, determina o novo estado e a palavra a ser gravada (na pilha). � Possui a facilidade de movimento vazio (análoga à do Autômato Finito), permitindo mudar de estado sem ler da fita. 34 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Autômato com Pilha � Um Autômato com Pilha Não-Determinístico (APN) ou simplesmente Autômato com Pilha (AP) M é uma 6- upla: � ∑ alfabeto de símbolos de entrada; � Q conjunto de estados possíveis do autômato o qual é finito; � δ função programa ou de função de transição: � q0 estado inicial do autômato tal que q0 é elementode Q; � F conjunto de estados finais tal que F está contido em Q; � V alfabeto auxiliar ou alfabeto da pilha. 35 Profa. Ellen Souza - https://sites.google.com/site/ellenuast M = (∑ , Q, δ, q0, F, V) δ: Q x (∑ ∪ { ε, ? }) X (V ∪ {ε , ? }) → 2 QxV* Autômato com Pilha � Características da função programa : � A função pode não ser total, ou seja, indefinida para alguns argumentos do conjunto de partida; a omissão do parâmetro de leitura, representada por "?", indica o teste de pilha vazia ou toda palavra de entrada lida; � O símbolo ε na leitura indica a facilidade de movimento vazio da fita ou da pilha (o autômato não lê nem move a cabeça). Note-se que, para o movimento ser considerado não determinístico, é suficiente que o movimento seja vazio na fita; � o símbolo ε na gravação indica que nenhuma gravação é realizada na pilha (e não move a cabeça). 36 Profa. Ellen Souza - https://sites.google.com/site/ellenuast 04/05/2012 7 Autômato com Pilha � Características da função programa : � Por exemplo, δ (p, ?, ε) = { (q, ε) } indica que no estado p se a entrada foi completamente lida, não lê da pilha, assume o estado q e não grava na pilha � A função programa pode ser representada como um grafo direto 37 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Autômato com Pilha � O processamento de um Autômato com Pilha, para uma palavra de entrada w, consiste na sucessiva aplicação da função programa para cada símbolo de w (da esquerda para a direita) até ocorrer uma condição de parada. � É possível que um Autômato com Pilha nunca atinja uma condição de parada. Neste caso, fica processando indefinidamente (ciclo ou loop infinito). 38 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Autômato com Pilha � Um Autômato com Pilha pode parar aceitando ou rejeitando a entrada ou ficar em loop infinito, como segue: � Um dos caminhos alternativos assume um estado final: o autômato pára e a palavra é aceita; � Todos os caminhos alternativos rejeitam a entrada: o autômato pára e a palavra é rejeitada; � Pelo menos um caminho alternativo está em loop infinito e os demais rejeitam (ou também estão em loop infinito): o autômato está em loop infinito. 39 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Autômato com Pilha � As seguintes notações são adotadas (suponha que M é um Autômato com Pilha): � ACEITA (M) ou L(M): conjunto de todas as palavras de ∑* aceitas por M; � REJEITA (M): conjunto de todas as palavras de ∑ * rejeitadas por M; � LOOP (M): conjunto de todas as palavras de ∑ * para as quais M fica processando indefinidamente. 40 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Autômato com Pilha � Exemplo 6: Autômato com Pilha � Considere a seguinte linguagem: L1 = { an bn | n > 0 } � O Autômato com Pilha M1 = ({a, b}, {q0, q1, qf}, δ1, q0, {qf}, {B }), onde δ1 é como abaixo, é tal que ACEITA(M1) = L1 � δ1 (q0, a, ε) = { (q0, B)} � δ1 (q0, b, B) = { (q1, ε)} � δ1 (q0, ?, ?) = { (qf, ε)} � δ1 (q1, b, B) = { (q1, ε)} � δ1 (q1, ?, ?) = { (qf, ε)} 41 Profa. Ellen Souza - https://sites.google.com/site/ellenuast Autômato com Pilha � Exemplo 7: Autômato com Pilha � Considere a seguinte linguagem: L3 = {wwr | w pertence a {a, b * } 42 Profa. Ellen Souza - https://sites.google.com/site/ellenuast
Compartilhar