Autômatos de Pilha e Linguagens Livres de Contexto - Forma Normal de Chomsky e Limites dos APs

TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 122 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte CAPÍTULO 2 Autômatos de Pilha e Linguagens Livres de Contexto 2 Forma Normal de Chomsky 2 Lema para o Teorema 24 3 Teorema 24 4 Definição Forma Normal de Chomsky 7 Exercícios 8 23 OS LIMITES DOS APS 11 O Escopo das Linguagens Livres de Contexto 11 Teorema 25 Lema do Bombeamento para Linguagens Livres de Contexto 11 APs Determinísticos 15 Teorema 26 17 O Princípio Lookahead 20 Exercícios 22 TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 222 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte CAPÍTULO 2 Autômatos de Pilha e Linguagens Livres de Contexto Forma Normal de Chomsky Um benefício de classificar linguagens em termos de gramáticas é que tais classificações fornecem insights sobre as estruturas das strings que podem aparecer nas linguagens correspondentes À primeira vista no entanto a flexibilidade permitida em gramáticas livres de contexto parece colocar pouca restrição sobre as estruturas das strings que potencialmente podem ser encontradas em linguagens livres de contexto Por isso pode ser surpreendente saber que as linguagens livres de contexto têm gramáticas cujas regras de reescrita seguem formatos extremamente rígidos Vamos então investigar mais profundamente a estrutura das regras de reescrita encontradas em gramáticas livres de contexto Começamos considerando a necessidade de λregras em uma gramática livre de contexto Se a linguagem gerada pela gramática contém a string vazia então pelo menos uma regra λ deve aparecer na gramática caso contrário é claro não haveria maneira de derivar a sequência vazia a partir do símbolo de início da gramática No entanto λ regras são necessárias se a linguagem a ser gerada não contém a sequência vazia Para responder a esta pergunta notese que a existência de uma λregra pode permitir que outros nãoterminais além do que aparece na regra sejam reescritos como a sequência vazia Por exemplo se uma gramática contém as regras Nλ e MN então M e N poderiam ser reescritas como λ ainda que a regra M λ possa não estar na gramática Para identificar o efeito das regras λ em uma gramática livre de contexto devemos isolar todos os nãoterminais que podem ser reescritos como a sequência vazia Para este fim definimos uma cadeia λ de comprimento n para ser uma sequência de regras da forma Vn Vn1 Vn1 Vn2 V0 λ O nãoterminal Vn é a origem da cadeia Agora se G é uma gramática livre de contexto que não gera a sequência vazia definimos U0 como o conjunto de nãoterminais que geram λ diretamente Criamos então um novo conjunto U1 que contém todos os elementos de U0 e cada nãoterminal que gera λ em um passo através de algum elemento de U0 Em seguida criamos um conjunto U2 onde U1 U2 e com cada nãoterminal N tal que N M é regra de G onde M U1 U0 Prosseguimos assim até criarmos Uk Uk1 Uk que inclui cada nãoterminal N tal que N M é regra de G onde M Uk1 Uk2 e Uk1 Uk Formalmente Uk é o fecho da operação de transitividade para alcançar λ a partir dos elementos de U0 Ou seja Uk contém todos os nãoterminais em G que podem ser reescritos como a sequência vazia Renomeamos o conjunto Uk por U Observe que uma vez que G não gera a sequência vazia U não contém o símbolo inicial de G TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 322 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte Se G fosse a gramática do Quadro 28 a que é uma gramática livre de contexto que não gera a string vazia então U0 seria Q e U1 seria P Q e U U1 Quadro 28a S zPzQz P xPx P Q Q yPy Q λ Agora para cada regra de reescrita da forma N w onde w é uma sequência com necessariamente terminais e não terminais adicionamos à G todas as regras da forma N s onde s é qualquer sequência não vazia obtida a partir de w através de uma ou mais ocorrências de nãoterminais pertencentes a U Com relação à gramática do Quadro 28a U P Q Portanto adicionaríamos as seguintes regras à gramática S zPzz S zzQz S zzz P xx Q yy Observe que não adicionamos a regra P λ que seria obtida a partir da regra P Q pois é uma regra que só inclui nãoterminais O Quadro 28b apresenta a gramática que gera a mesma linguagem de 28a sem usar λ regras Quadro 28b S zPzQz S zzQz S zPzz S zzz P xPx P xx P Q Q yPy Q yy Tendo adicionado essas novas regras à gramática não precisamos mais das regras λ Vamos formalizar isso Lema para o Teorema 24 Seja G uma gramática livre de contexto que não gera a sequência vazia λ Seja RG o conjunto de regras de G Seja Rλ o conjunto de regras λ Seja U é o conjunto de todos os nãoterminais que podem ser reescritos como λ por uma ou mais operações conforme definido no preâmbulo deste Lema Seja RU o conjunto de regras obtido tomando cada regra em RG da forma N w onde w é uma sequência de terminais e não terminais e criando outra N s onde s é uma sequência não vazia obtida pela remoção em w de uma ou mais ocorrências de não terminais pertencentes a U Seja H a gramática cujo conjunto de regras é RH RG RU Rλ Dadas estas definições a gramática livre de contexto H é equivalente à gramática G sem as regras λ TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 422 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte Extra Prova Suponha que uma derivação de uma sequência usando a gramática original exigisse a aplicação de alguma regra λ e seja N a origem da cadeia λ mais longa que aparece na derivação que termina com essa regra λ Então esta ocorrência de N deve ser introduzida na derivação pela aplicação de alguma regra da forma M w1Nw2 onde w1 e w2 são cadeias de terminais e não terminais um dos quais deve ser não vazio Note que N não pode ser o símbolo inicial pois N U e S U pois G não gera λ A regra M w1w2 está no conjunto RU Portanto podemos eliminar o uso da λregra na derivação usando a regra M w1w2 em vez de M w1Nw2 H não pode gerar sequências que não foram geradas por G Afinal qualquer das regras que foram adicionadas podem ser simuladas por sequências curtas de regras da gramática original Assim concluímos que qualquer linguagem livre de contexto que não contenha a sequência vazia pode ser gerada por uma gramática livre de contexto sem λregras fimprova Como exemplo supondo que G é a gramática do Quadro 28a a derivação de zxxzz através da sequência S zPzQz zxPxzQz zxQxzQz zxxzQz pode ser derivada pela gramática H relacionada com G e mostrada na Figura 29b com menor número de derivações S zPzz zxxzz Usando esta conclusão como trampolim podemos provar o seguinte teorema Teorema 24 Se L é uma linguagem livre de contexto que não contém a sequência vazia então existe uma gramática livre de contexto G que gera L G L e o lado direito de qualquer regra de reescrita em G consiste em um único terminal como em N x ou exatamente dois nãoterminais como em N PQ Prova Considere uma linguagem livre de contexto L tal que λ L Sabemos pelo Lema anterior que existe uma gramática que gera L sem regras λ Devemos mostrar que existe uma TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 522 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte gramática deste tipo que a gera e além disso atende as restrições de regras de produção do enunciado do teorema1 Vamos construir tal gramática Seja G uma gramática livre de contexto que gera L Para cada terminal y em G introduzimos um novo e exclusivo Y nãoterminal e a regra de reescrita Y y Depois substituímos todas as ocorrências do terminal y nas outras regras de G por Y Isso produz uma gramática livre de contexto G1 em que o lado direito de cada regra de reescrita é um único terminal ou uma sequência de nãoterminais e L G1 L G L Agora substituímos cada regra em G1 que está forma N N1 N2Nm onde m 2 pela coleção de regras N N1 R1 Rl N2 R2 Rml Nm1Nm Onde cada Rk é um novo nãoterminal que não aparece em em G1 Claramente esta modificação não altera a linguagem gerada pela gramática Nesta fase temos uma gramática livre de contexto G2 que gera L e para a qual o lado direito de cada regra de reescrita é um único terminal dois nãoterminais ou um único nãoterminal Daí a tarefa restante é remover as regras desta última forma Para fazer isso procedemos conforme a criação de Rλ Seja Z um conjunto de regras inicialmente vazio e seja W um conjunto de regras inicialmente igual à G2 Para cada nãoterminal M obtemos Y0 conjunto formado por todo nãoterminal N tal que N M seja regra de G2 Seja Y o fecho da operação de transitividade para alcançar M a partir dos elementos de Y0 Se M x é uma regra em G2 então para cada P Y introduza a regra P x em Z Além disso se se M AB está em G2 A e B não terminais também introduza em Z a regra P AB Finalmente retire N M de W A gramática G3 W Z obtida ao final destes procedimentos não terá regras cujo lado direito contém um único nãoterminal e não reduz os poderes geradores da gramática G2 Afinal qualquer derivação que usou as regras da forma M N poderia ser modificada para usar as regras introduzidas Assim a gramática resultante G3 gera L e satisfaz as restrições do teorema fimprova 1 Repare que a gramática daFigura 210b sem regras λ gera a mesma linguagem da gramática da Figura 210a mas não satisfaz as restrições do enunciado do Teorema 24 TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 622 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte Para esclarecer os passos da prova anterior considere como eles afetariam a gramática G no Quadro 29a com o símbolo de início S Quadro 29a Gramática G O primeiro passo seria introduzir os novos nãoterminais X Y e Z e converter a gramática para a gramática G1 mostrada no Quadro 29b Quadro 29b Gramática G1 Em seguida a regra S ZMZ seria substituída pelo par S ZR1 e R1 MZ A regra M YMY seria substituídas por M YP1 e P1 MY Então obteríamos a gramática G2 do Quadro 29c Quadro 29c Gramática G2 Finalmente a sequência N X e a sequência M N e N X dariam origem às regras N x e M x produzindo a gramática G3 mostrada no Quadro 29d Quadro 29d Gramática G3 TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 722 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte Definição Forma Normal de Chomsky Uma gramática cujas regras de reescrita estão em conformidade com as restrições do Teorema 24 é dita estar em Forma Normal de Chomsky Por exemplo a gramática S XM M SY X x Y y cujo símbolo inicial é S está na forma normal de Chomsky enquanto S xSy S xy que gera a mesma linguagem não está na forma normal de Chomsky Em resumo o Teorema 24 diz que qualquer linguagem livre de contexto que não contenha a sequência vazia pode ser gerada por uma gramática livre de contexto na forma normal de Chomsky Embora seja limitado a um subconjunto das linguagens livre de contexto esta caracterização é ainda bastante geral Por exemplo a maioria das linguagens em configurações aplicadas como linguagens de programação não contêm a sequência vazia Mesmo para as linguagens que contêm a string vazia a caracterização na Forma Normal de Chomsky ainda tem mérito De fato se uma linguagem livre de contexto L contém λ podemos encontrar uma gramática livre de contexto que é quase na forma normal de Chomsky mas ainda gera L Tal gramática H seria obtida assim Passo 1 Encontramos uma gramática livre de contexto G na Forma Normal de Chomsky que gera L λ Seja S o símbolo de início de G Seja RG o conjunto de regras de G Passo 2 Construa RH o conjunto de regras da gramática H da seguinte forma Passo 21 Coloque todas as regras de G em RH Passo 22 Crie um novo símbolo de início Z e introduza a regra Z λ em RH Passo 23 Para cada regra com lado esquerdo S crie uma regra com mesmo lado direito mas com lado esquerdo Z Claramente a gramática H irá gerar as strings e somente as strings da linguagem L A introdução do novo símbolo de início Z elimina a possibilidade de a regra λ interagir com outras regras na gramática Consequentemente mesmo linguagens livres de contexto que contém a sequência vazia podem ser geradas por gramáticas que estão quase na forma normal Chomsky Veja o exemplo do Quadro 210 Quadro 210 Gramática para L λ Gramática para L com símbolo de início S Z λ Z MN S MN S MN N MS N MS N x M x N x M x TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 822 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte Exercícios 1 Mostre que cada sequência derivada de uma gramática livre de contexto por uma derivação mais à esquerda também pode ser derivada por uma derivação mais à direita Dica Fica fácil referenciando a linguagem gerada pela gramática equivalente que esteja na Forma Normal de Chomsky em que cada derivação é sobre uma regra com dois nãoterminais ou que leve a um terminal A árvore binária associada é única A derivação pela esquerda seria uma travessia em préordem e pela esquerda seria em pósordem considerando que a ação de visitação é a impressão do símbolo na regra de derivação de terminal e nula na regra de derivação de dois nãoterminais 2 Uma gramática que permite mais de uma árvore de análise para uma única sequência é considerada ambígua2 Mostre que a gramática abaixo é ambígua mostrando que a string ictictaea tem derivações que possuem árvores de análise distintas S ictS S ictSeS S a Veja que i poderia estar representando if c poderia estar representando uma condição booleana t representando then e representando else e a representando uma instrução 3 Opcional Utilize o procedimento descrito no Teorema 23 para construir uma gramática livre de contexto que gere a linguagem aceita pelo AP cujo diagrama de transição é mostrado abaixo Este exercício é para que o aluno tenha noção do tamanho do trabalho que é obter a gramática através daquele procedimento que foi montado apenas para a demonstração do teorema Neste caso a linguagem do AP é formada pelo conjunto de strings cwc onde w é λ ou é uma string que alterna subsequências de gs sempre 2 No texto do capítulo 4 vamos mostrar no Apêndice C Seção Cl que o problema de determinar se uma gramática qualquer é am bígua é insolúvel ou seja não admite algoritmo de solução TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 922 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte seguidas de subsequências de fs onde o comprimento da késima sequência de fs é menor ou igual à diferença entre o somatório dos comprimentos das k sequências de gs anteriores e o somatório dos comprimentos das k1 sequências de fs anteriores com exceção da última sequência de fs onde deve haver a igualdade Formalmente se l k é o comprimento da késima sequência de fs e s k é o comprimento da késima sequência de gs Se há K duplas de subsequências l K será igual à diferença A obtenção de uma gramática para esta linguagem por pura análise da descrição não é fácil A obtenção pelo procedimento dado no Teorema 23 gera uma gramática correta mas enorme Vamos fazer um pouco este procedimento 0 Os nãoterminais de G consistem no símbolo inicial S juntamente com todos os objetivos possíveis de M ou seja todas as estruturas sintáticas da forma p x q em que p q são estados e x pode ser λ ou um símbolo de pilha Então os nãoterminais serão r λ s r λ t r c s r c t r g s r g t r λ r r g r s λ r s λ t s c r s c t s g r s g t s λ s s g s t λ r t λ s t c r t c s t g r t g s t λ t t g t 1 Para cada estado de aceitação f de M introduza a regra de reescrita S 𝔦𝔦 λ f onde 𝔦𝔦 é o estado inicial de M S r λ t 2 Para cada estado p em M introduza a regra de reescrita p λ p λ r λ r λ s λ s λ t λ t λ 3 Para cada transição p x y q z y λ introduza a regra p y e x q z e para cada estado e s f g s λ vai produzir as regras s g r f s λ r s g s f s λ s s g t f s λ t s λ c t λ vai produzir as regras TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1022 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte s c r c t λ r s c s c t λ s s c t c t λ t 4 Para cada transição da forma p x λ q z introduza a regra p w e x q z k k w e para cada tripla w e k onde w é um símbolo de pilha ou λ k e e são estados podendo ser iguais Para este problema específico w λ c g k r s t e r s t Ou seja são 9 triplas para cada regra As transições do tipo mencionando sem retirada de símbolo da pilha são r c λ s c e s g λ s g Portanto são 18 regras obtidas desta forma Fica a critério do aluno apresentar estas regras e eventualmente mostrar algum exemplo de produção de string da linguagem 4 Mostre que a união de duas linguagens livres de contexto é livre de contexto Para isso mostre como duas gramáticas livres de contexto para as linguagens originais podem ser combinadas para formar uma gramática livre de contexto que gera a união Dica Use a forma normal de Chomsky 5 Converta a seguinte gramática G com o símbolo de início S para uma gramática na forma normal Chomsky que gera a mesma linguagem RG S xSy S wNz N S N λ TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1122 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte 23 OS LIMITES DOS APS Até aqui caracterizamos as linguagens livres de contexto tanto como as linguagens que são geradas por gramáticas livres de contexto quanto como aquelas linguagens aceitas por APs No entanto não questionamos se há ou não linguagens que não são livres de contexto Além disso os APs que vimos até agora foram nãodeterminísticos e uma vez que uma das aplicações desta teoria é desenvolver ferramentas de projeto de compiladores com base nas propriedades de APs precisamos compreender o papel do determinismo concernentes a APs Estas são as questões abordadas nesta seção O Escopo das Linguagens Livres de Contexto Aqui vamos apresentar uma linguagem que não é livre de contexto Para isso usamos o teorema conhecido como o lema de bombeamento para linguagens livres de contexto Teorema 25 Lema do Bombeamento para Linguagens Livres de Contexto Se L é uma linguagem livre de contexto que contém um número infinito de strings finitas então deve haver um inteiro n tal que toda string s L de comprimento s n pode ser partida em cinco strings r u w v e t cuja concatenação gera s ruwvt e uv 0 ou seja u λ ou v λ uwv n ou seja a parte do meio não é tão longa rukwvkt L para cada k ℕ redação obedecendo os livros do Spiser e do HopcroftUlman Prova Seja L uma linguagem livre de contexto contendo um número infinito de strings e seja G uma gramática livre de contexto tal que LG L Para simplificar as ilustrações considere que G está na Forma Normal de Chomsky Se a linguagem aceita λ vimos anteriormente que com uma pequena mudança teríamos quase que exatamente a Forma Normal de Chomsky Isto facilita porque a árvore de derivação da gramática seria binária Então o número máximo de símbolos do lado direito é 2 Se a árvore de dedução de uma string z da linguagem tem profundidade d isto significa que s 2d Agora supondo que N é o número de símbolos nãoterminais em G escolha uma string em L de comprimento maior do que 2N Então qualquer árvore de análise T para essa cadeia deve ter profundidade maior do que N Isto implica que há um caminho p em T desde a raiz até uma folha contendo mais do que N nãoterminais Consequentemente algum nãoterminal X deve aparecer pelo menos duas vezes no caminho TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1222 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte Isto posto considere a subárvore de T cuja raiz é o nó onde está a primeira ocorrência de X a mais próxima da raiz Considere também a próxima ocorrência de X no caminho p A Figura 28 ilustra esta situação A Figura 28 apresenta a árvore de derivação de uma string s ruwv cada substring é o que é produzido pelo garfo acima dela A ilustração é uma simplificação Se D não é o filho direito do primeiro X mas é pai do segundo X haveria várias ramificações entre o primeiro X e D compondo u Se E não é o filho direito de D então haveria várias ramificações entre D e E compondo v Um raciocínio análogo pode ser aplicado A e o primeiro X para compor r e entre S e B para compor t Repare que se X produziu um ramo encabeçado com X o retângulo pequeno este ramo pode ser substituído para fazer a mesma derivação do seu antecessor indicada pelo retângulo grande A situação é mostrada na Figura 29 derivação da string ruuwvvt Ou seja da string ru2wv2t k 2 Da mesma forma a subárvore encabeçada pelo primeiro X retângulo grande pode ser substituída pela subárvore encabeçada pelo segundo X retângulo pequeno produzindo a string rwt k 0 r t w u v Figura 28 A B C D E TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1322 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte Este padrão de substituições pode se repetir ilimitadamente ie para qualquer k ℕ fimprova Figura 29 TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1422 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte Exemplo Podemos provar que a linguagem L xnynzn n ℕ não é livre de contexto utilizando o teorema Suponha que N é o inteiro tal que toda string z L z N obedece ao enunciado do teorema Considere a string s xNyNzN Essa string obviamente pertence à L Suponha que L é livre de contexto Então haveria uma partição de s em cinco strings r t u v w s ruwvt que seguiria as determinações do teorema Mas uwv N Então uwv pode ser igual a uma das seguintes possibilidades a uwv xρ para algum 1 ρ N b uwv yτ para algum 1 τ N c uwv zσ para algum 1 σ N d uwv xψ yζ para uma dupla ψ ζ 1 ψ ζ N e uwv yα zβ para uma dupla α β 1 α β N Qualquer repetição mútua de u e v em a faria com que houvesse um número maior de xs do que de ys e zs claramente as strings produzidas não pertenceriam à L A situação é análoga para os casos de b e c mas determinando um número maior de ys em b e um número maior de zs em c No caso d o número de zs já ficaria menor do que o número de xs ou de ys para ru2wv2t pois os zs estão todos em t e este não é aumentado O caso e é análogo fimexemplo O fato de que a linguagem xnynzn n ℕ não é livre de contexto pode parecer insignificante portanto vamos considerar um exemplo em que tais padrões ocorrem Dentro de um processador de texto típico palavras sublinhadas a serem impressas às vezes são armazenados como uma cadeia de símbolos as palavras propriamente ditas seguido pelo mesmo número de símbolos de backspaces seguido pelo mesmo número de símbolos de sublinhado Tais palavras sublinhadas portanto constituem cadeias que estão em conformidade com o padrão xnynzn onde os xs são letras das palavras os ys são backspaces e os zs são símbolos de sublinhado Consequentemente o Teorema 25 nos diz que um APs não seria suficiente para construir uma rotina de análise capaz de reconhecer essas palavras sublinhadas Se este exemplo parece um tanto artificial é porque a coleção de linguagens livres de contexto estão próximas de englobar as estruturas encontradas em linguagens de programação típicas de hoje De fato os diagramas de sintaxe populares usados para expressar a sintaxe da linguagem de programação são essencialmente regras de reescrita livres de contexto Por outro lado ainda há vários recursos de linguagem que tais TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1522 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte diagramas não conseguem captar Os diagramas de sintaxe são incapazes de transmitir a restrição de que diferentes variáveis não podem ter o mesmo nome a restrição de que o número de parâmetros formais de um subprograma deve ser o mesmo que o número de parâmetros reais quando o subprograma é chamado a restrição de que as referências a identificadores indefinidos são ilegais etc No entanto o poder das gramáticas livres de contexto nos permite capturar um número significativo das regras de sintaxe das linguagens de programação de hoje e portanto vale a pena usar nosso tempo para desenvolver técnicas de análise com base nas propriedades de APs Na verdade é com tais técnicas que muitos compiladores são construídos Nestes casos os recursos de linguagem que se encontram fora do alcance de gramáticas livres de contexto são tratadas como casos especiais ou então avaliados como parte da análise semântica e não nas rotinas de análise sintática APs Determinísticos Resta um problema a resolver antes de voltar nossa atenção para a produção de rotinas de análise de APs Os APs até agora têm sido nãodeterminísticos e nossas rotinas de compilador devem ser determinísticas Se quisermos usar APs como ferramentas de projeto para desenvolver rotinas de análise determinística devemos conhecer quais limitações são encontradas ao se exigir um comportamento determinístico para nossos APs Nosso primeiro passo nesta direção é introduzir o conceito de APs determinístico Falando de forma geral um AP determinístico é um AP no qual em qualquer momento uma única transição é aplicável Isso implica que se p x y q z e p x y r w são transições do autômato então q deve ser igual a r e z deve ser igual a w No entanto esta condição por si só não exclui a possibilidade de não determinismo Por exemplo se o símbolo de entrada seguinte fosse x a presença de transições p λ y q z e p x y q z proporcionaria a escolha de mover se do estado p ignorando a entrada ou moverse do estado p consumindo a entrada Um problema semelhante ocorreria se uma máquina com y no topo de sua pilha tivesse a escolha entre p x λ q z e p x y q z A máquina deve moverse do estado p ignorando a pilha ou movese do estado p enquanto retira um símbolo da pilha Com base nessas observações definimos um AP determinístico Um AP S Σ Γ T i F é determinístico se Para cada tripla p x y S Σ Γ existe uma única transição p u v q z T onde u v x y x λ λ y λ λ q S e z Γ Por exemplo essa restrição retira a presença simultânea de p λ y q z e p x λ r s TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1622 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte Para enfatizar as sutilezas envolvidas no desenvolvimento de um AP determinístico suponha que queremos projetar uma parte de tal máquina de modo que quando ela está no estado p se um y está no topo da pilha a transição p x y q λ deve ser executada caso contrário não há y no topo da pilha a transição p x λ q λ será executada Não há incerteza envolvida nesta descrição mas o diagrama de transição simples mostrado na Figura 210a introduz a incerteza Figura 210a Em particular o diagrama permitiria à máquina fazer uma escolha quando o topo da pilha tivesse um y pois ambos p x y q λ e p x λ q λ seriam aplicáveis Para resolver esse problema seguimos a abordagem mostrada na Figura 210b onde assumimos que os símbolos de pilha da máquina são somente x y e Figura 210b Aqui introduzimos opções explícitas para a máquina tomar no caso de o símbolo no topo da pilha não ser um y Nesses casos a máquina é informada para retirar um símbolo da pilha e em seguida colocálo novamente Evidentemente esta abordagem requer que a pilha não esteja vazia quando a máquina está no estado p caso contrário nenhuma das transições seria aplicável É por isso que introduzimos o símbolo de pilha que deve ser colocado no fundo da pilha no início de qualquer computação e mantido lá até o final Ao desenhar diagramas para APs determinísticos muitas vezes representaremos somente as transições que são pertinentes para a tarefa que temos em mãos para evitar diagramas muito confusos A exigência de se ter determinismo reduz o poder dos APs como mostrado pelo teorema a seguir TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1722 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte Teorema 26 Existe uma linguagem livre de contexto que não é aceita por qualquer AP determinístico Prova Vamos mostrar que a linguagem L xnyn n ℕ xn y2n n ℕ é livre de contexto mas não pode ser aceita por AP determinístico Primeiro observe que a Figura 211 mostra um diagrama de transição para um AP que aceita L Figura 211 Assim L é livre de contexto Para mostrar que L não pode ser aceito por qualquer AP determinístico vamos usar uma prova por contradição Suponha então que M é um AP determinístico tal que LM L Usando M construímos um outro AP da seguinte maneira 1 Crie duas cópias de M chamadas M1 e M2 Os estados em M1 e M2 serão chamados primos se são cópias do mesmo estado em M 2 Remova o status de aceitação dos estados de aceitação de M1 e remova status de inicial do estado inicial de M2 3 Mude o estado de destinação de cada transição originado de um antigo estado de aceitação de M1 para seu primo em M2 Essas transições alteradas formam ligações entre M1 e M2 de tal forma que as duas máquinas se tornam um único AP 4 Modifique todas as transições que lêem y da entrada e têm seus estados de destino em M2 incluindo aquelas novas transições criadas possivelmente na etapa 3 tal que leiam em vez disso o símbolo z TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1822 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte A nossa proposição é a linguagem aceita pelo autômato construído desta forma a partir de M1 e M2 seria xnynzn n ℕ De fato se a esta máquina fosse dada uma string de entrada da forma xnynzn ela teria que alcançar um dos antigos estados de aceitação de M1 depois de ler os xs e ys mas antes de ler qualquer z O AP determinístico original M teria aceitado xnyn e uma vez que é determinístico deve atingir o mesmo estado depois de ler xnyn independentemente dos símbolos que possam seguir Neste ponto a execução mudaria para M2 por causa do passo 3 acima onde o z na string de entrada levaria a um estado de aceitação Afinal M2 procederia como se estivesse processando a última porção de uma string da forma xny2n mas uma vez que suas instruções de leitura foram alteradas ela iria realmente ler zs em vez de ys Para ver que apenas as cadeias da forma xnynzn poderiam ser aceitas observe que para alcançar um estado de aceitação requer que M1 processe uma string da forma xnyn para transferir o controle para M2 e então M2 encontre n ocorrências de zs pois M2 prossegue como se estivesse processando a última parte de xny2n Vemos então que nossa suposição de que L pode ser aceito por um autômato de pilha determinístico leva à conclusão de que a linguagem xnynzn n ℕ é livre de contexto Mas sabemos que isso é falso Conseqüentemente nossa suposição deve estar errada L não pode ser aceito por um AP determinístico fimprova Nos referimos às linguagens que são aceitas por APs determinísticos naturalmente como as linguagens determinísticas livres de contexto Esta classe de linguagens é um subconjunto da classe de linguagens livres de contexto Na verdade há um outro problema grave Os APs determinísticos que estamos considerando aceitam cadeias sem necessariamente esvaziar suas pilhas e como mencionado anteriormente esse modelo é susceptível de levar a segmentos de programas que entupem a memória de um computador com resquícios de operações anteriores Infelizmente esse problema é mais sério para os APs determinísticos do que para os APs comuns uma vez que não podemos modificar todos os APs determinísticos para que eles esvaziem a pilha antes de chegar a um estado de aceitação Vamos dar um exemplo de uma linguagem que é aceita por um AP determinístico portanto é uma linguagem livre de contexto determinística que está representado pelo diagrama da Figura 212 A linguagem que este AP determinístico aceita é a linguagem L xn n ℕ xnyn n ℕ TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1922 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte este autômato certamente não limpa a pilha quando chega no estado final p Nós afirmamos que L não pode ser aceito por algum outro AP determinístico que requeira o esvaziamento de sua pilha antes de chegar a um estado de aceitação De fato se houvesse um AP M que fizesse isso e fosse dada uma entrada da forma xnyn a máquina M teria que alcançar um estado de aceitação com uma pilha vazia depois de ler cada x Explicando Uma vez que M é determinística ela deve seguir o mesmo caminho de execução enquanto processa os xs em xnyn que seguirá ao processar qualquer sequência de xs e uma vez que qualquer sequência de xs já é em si uma string aceitável a máquina deve esvaziar sua pilha e mover para um estado de aceitação após ler cada x Agora se escolhemos n maior do que o número de estados em M podemos concluir que em algum ponto ao processar os xs na cadeia xnyn a máquina deve estar em algum estado p com sua pilha vazia pelo menos duas vezes Se m é o número de xs lidos entre essas visitas a p M deve aceitar a string xnmyn o que contradiz a definição de M Há uma hierarquia de linguagens associada a APs isso é ilustrado na Figura 213 Figura 212 TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 2022 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte Figura 213 O Princípio Lookahead Nesse ponto a esperança de desenvolver segmentos de programa utilizáveis para analisar uma ampla classe de linguagens pode começar a desaparecer Parece que qualquer técnica desenvolvida estará restrita à menor classe das linguagens apresentadas na Figura 213 Felizmente a situação melhora se reconsiderarmos a maneira pela qual os autômatos aceitam cadeias Lembrese que para aceitar uma string um AP deve satisfazer seu critério de aceitação depois de ler a sequência mas sem mover o cabeçote de leitura de fita mais para adiante na fita Isso significa que um AP deve atingir um estado de aceitação sem realmente ler um marcador de fim de cadeia O resultado é o que poderíamos considerar um processo de aceitação passiva em que a máquina deve tropeçar em uma configuração de aceitação sem que seja dito para fazêlo por um marcador de fim de cadeia Em contraste se imaginarmos um sistema pelo qual a máquina poderia espiar o próximo símbolo em sua fita sem realmente avançar seu cabeçote de leitura da fita ele poderia detectar um marcador de fim de cadeia que se aproxima e executar atividades especiais de encerramento que não teria executado sem essa possibilidade de espiar uma posição mais adiante Linguagens livres de contexto Linguagens livres de contexto determinísticas Linguagens aceitas por APs determinísticos que esvaziam suas pilhas antes de aceitar uma string TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 2122 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte Iremos nos referir à técnica de espiar os símbolos futuros sem realmente lêlos3 como o princípio lookahead literalmente ver adiante Sua aplicação é exemplificada pela estrutura de loop while exibida no segmento de programa escrito em pseudocódigo Quadro 211 Este segmento essencialmente espia o próximo símbolo e usa as informações obtidas para decidir se deve ou não processar o símbolo dentro da estrutura while É dentro das várias opções de casos que a rotina finalmente decide se vai consumir o símbolo e se preparar para processar outro Quadro 211 read symbol while symbol endofstring switchsymbol case x pilhapush y read symbol break case y exit to error routine case z pilhapush read symbol end while Assim a variável symbol é realmente um lugar de retenção ou buffer para o próximo símbolo de entrada Um símbolo retido em symbol pode ser considerado ao fazer decisões mas não necessita ser consumido ou ser lido oficialmente até que a decisão de processálo seja feita Em particular o marcador de fim de cadeia não será consumido por esta rotina mas permanecerá no buffer após a estrutura while ter terminado onde estará disponível como entrada para a próxima rotina Afinal em um compilador real o marcador de fim de cadeia pode muito bem ser o primeiro símbolo da próxima estrutura a ser analisada Vemos então que a aplicação do princípio lookahead é uma técnica de programação básica e comum quase trivial Também estamos prestes a ver que ao aplicar este princípio ao converter os APs em segmentos de programa podemos construir programas que superem o não determinismo encontrado em alguns APs Assim a teoria dos APs fornece uma base a partir da qual a análise de rotinas para uma ampla gama de linguagens livres de contexto pode ser desenvolvido Como isso é feito é o assunto das próximas duas seções 3 consumílos seria melhor no sentido de que o deslocamento do cabeçote de leitura de um autômato representa a leitura do anterior TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 2222 tradução livre e adaptação do livro de J Glenn Brookshear CAPÍTULO 2 2ª parte Exercícios 1 Aplique o Teorema 25 para provar que a linguagem xmynxmynxmyn m n N não é livre de contexto 2 Dê exemplos de cada uma das seguintes linguagens a Uma linguagem que não é livre de contexto Exercício 1 b Uma linguagem que é livre de contexto mas não determinística Teorema 26 c Uma linguagem que é determinística livre de contexto mas não é aceita por um AP determinístico que deve esvaziar a sua pilha ver Figura 212 d Uma linguagem que é aceita por um AP determinístico que deve esvaziar a sua pilha mas não é regular ver Figura 22 3 Desenhe a parte pertinente de um diagrama de transição para um AP determinístico que a partir do estado p irá mover para o estado q ao ler um x enquanto retira um y e coloca um z se o topo da pilha contém um y ou irá mover para o estado q quando lê um x sem retirar nada da pilha e colocando um z se o topo da pilha não é um y Suponha que o alfabeto da pilha é Γ x y z w 4 Identifique as situações que gerariam incertezas na execução de um AP contendo as transições p λ y q z e p x λ r w