Autômatos de Pilha e Linguagens Livres de Contexto - Teoria e Exercícios

TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 127 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte CAPÍTULO 2 Autômatos de Pilha e Linguagens Livres de Contexto 2 21 AUTÔMATOS DE PILHA 3 Definição de Autômato de Pilha APs 3 Autômatos de Pilha como aceitadores de linguagem 6 Autômatos de Pilha que terminam com pilha vazia 7 Teorema 21 8 Exercícios 10 22 GRAMÁTICAS LIVRES DE CONTEXTO 11 Definição 11 Gramáticas Livres de Contexto e APs 13 Teorema 22 14 Exemplo de criação de AP a partir de uma gramática livre de contexto 15 Teorema 23 18 Exemplo de criação de gramática livre de contexto a partir de um AP 20 ANEXO 1 Continuação da prova do Teorema 23 26 Teorema 23 26 TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 227 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte CAPÍTULO 2 Autômatos de Pilha e Linguagens Livres de Contexto No capítulo anterior vimos como os analisadores lexicais podem ser construídos usando os princípios de autômatos finitos e investigamos as linguagens regulares que são as linguagens que esses autômatos são capazes de reconhecer Também descobrimos que as técnicas simples associadas com autômatos finitos são limitadas Em particular descobrimos que os sistemas de análise baseados em AFs não são capazes de lidar com muitas das estruturas de sintaxe que ocorrem em linguagens de programação por exemplo um AF não consegue verificar que para cada abre parênteses há um e apenas um fecha parênteses posterior Neste capítulo generalizamos os conceitos de autômatos finitos e gramáticas regulares para obter técnicas de análise para uma classe de linguagens mais abrangentes denominadas linguagens livres de contexto Os autômatos que reconhecem estas linguagens têm um sistema de memória interna na forma de pilha A introdução deste mecanismo de memória simples aumenta significativamente o poder de processamento de linguagem destes autômatos em relação aos autômatos finitos e fornece um contexto no qual são formulados vários algoritmos eficientes de análise Para gerar as linguagens reconhecidas pelos autômatos de pilha usaremos novamente o conceito de gramática Neste caso permitimos uma maior complexidade na estrutura das regras de reescrita Essas novas regras permitem criar as gramáticas que geram as linguagens livres de contexto isto é as gramáticas livres de contexto É por meio de tais gramáticas que a sintaxe da maioria das linguagens de programação é descrita TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 327 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte 21 AUTÔMATOS DE PILHA Vimos no Capítulo anterior que não há autômato finito capaz de reconhecer a linguagem L xnyn n N Colocamos como hipótese que este problema ocorria porque AFs não têm memória de quantos xs foram usados na 1ª parte da string de entrada Veremos que os Autômatos de Pilha reconhecem essa linguagem Definição de Autômato de Pilha APs Aqui introduzimos a classe de máquinas conhecidas como autômatos de pilha1 Vamos denotar essa classe de máquinas pelo acrônimo AP O modelo da máquina é apresentado na Figura 20 Como acontece nos AFs a máquina tem um fluxo de entrada onde são lidos símbolos de um alfabeto Σ e um mecanismo de controle que pode estar em qualquer estado pertencente a um conjunto finito de estados Um único destes estados é designado como inicial e pelo menos um estado é designado de aceitação Os APs são dotados de uma pilha na qual podem armazenar informações para recuperar posteriormente Os símbolos que podem ser armazenados na pilha da AP são denominados símbolos de pilha O conjunto dos símbolos de pilha Γ é inclui os símbolos do alfabeto Σ da máquina 1 Uma pilha às vezes é chamada de armazenamento pushdown ou pilha pushdown pilha Direção de movimento da cabeça de leitura Cabeça de leitura Mecanismo de controle Fita de entrada Indicador de estado Figura 20 TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 427 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte e até símbolos adicionais normalmente usados como marcadores internos da máquina Por exemplo os marcadores podem ser usados para separar seções da pilha que devem ser interpretadas de formas diferentes Mais precisamente se uma máquina coloca um símbolo especial na pilha antes de realizar quaisquer outra operação então esse símbolo no topo da pilha pode ser usado como indicador de pilha vazia durante operações posteriores Aqui adotaremos o símbolo com esse propósito As transições executadas por um AP devem ser variações da seguinte sequência básica ler um símbolo da entrada retirar um símbolo do topo da pilha colocar um símbolo no topo da pilha e fazer uma transição de um estado para outro Denotamos esse processo pela notação p x s q y onde p estado corrente x o símbolo do alfabeto que é lido na entrada s o símbolo retirado do topo da pilha q o novo estado podendo ser igual ao estado corrente y o símbolo colocado no topo da pilha Formalmente um AP é uma sêxtupla S Σ Γ T 𝔦𝔦 F em que S é um conjunto finito de estados Σ é alfabeto da máquina Γ é o conjunto finito de símbolos de pilha T é o conjunto finito de transições T S Σ Γ S Γ 𝔦𝔦 S é o estado inicial F S é o conjunto de estados de aceitação Como no tratamento de AFs utilizamos a letra grega λ para representar a ausência de símbolo sequência vazia Alguns exemplos p λ s q y transição de p para q na qual não há leitura o símbolo s é retirado do topo da pilha e o símbolo y é colocado no topo da pilha p x λ q y transição de p para q na qual lêse o símbolo x nada é retirado da pilha e o símbolo y é colocado no topo da pilha p λ λ p y o símbolo y é colocado no topo da pilha sem que haja mudança de estado nem retirada de símbolo da pilha etc A coleção de transições possíveis é um dos parâmetros que definem um AP O AP só aceita sequências que geram apropriadamente as transições que estão em T TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 527 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Para ilustrar o AP usamos um diagrama de transição análogo àquele dos autômatos finitos No entanto no caso dos APs os rótulos vão em triplas que especificam os caracteres envolvidos na transição Por exemplo um arco de um estado q para um estado p que representa a transição p x y q z é rotulado com x y z Nesse texto para evitar aspas usaremos x y z para designar os rótulos Para facilitar a leitura usaremos frequentemente as letras P e E para indicar a pilha do e a fita a fita de entrada do AP respectivamente A Figura 21 mostra um diagrama de transição para um AP Nesse diagrama o conjunto de transições é formado por T 1 λ λ 2 2 x λ 2 x 2 y x 3 λ 3 y x 3 λ 3 λ 4 λ Na ordem os arcos dessas transições são rotulados com λ λ x λ x y x λ y x λ e λ λ O estado inicial é o estado 1 e os estados de aceitação indicados por anéis são o 1 e o 4 A primeira transição 1 λ λ 2 marca o fundo de P com o marcador Enquanto há caracteres iguais a x sendo lidos em sequência em E ele os vai colocando na pilha Isto é especificado pela transição 2 x λ 2 x Repare que não há outras transições do estado 2 para o estado 2 Então qualquer outra transição de 2 para ele mesmo envolvendo qualquer outro rótulo faz com que o AP rejeite a sequência A única transição possível de 2 para 3 é quando se lê um y e há um x no topo de P Nesse caso o AP retira esse x da pilha antes de ir para 3 Qualquer outra transição de 2 para 3 envolvendo qualquer outro rótulo faz com que o AP rejeite a sequência No estado 3 o AP permanece lá somente enquanto estiver lendo y em E e x está no topo da pilha caso em que ele simplesmente retira o x do topo Qualquer possibilidade de Figura 21 TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 627 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte leitura em E que não seja do símbolo y e tendo o símbolo x em P faz com que o AP rejeite a sequência O estado de aceitação só é alcançado transição de 3 para 4 se não há mais nada para ser lido em E e o AP chegou ao fundo da pilha situação marcada com o no fundo da pilha Se ainda houver algo em E o AP rejeita a sequência isso é representado pela ausência de outras transições onde está no topo da pilha Essas observações de aceitação relacionadas aos arcos que existem são muito importantes Sem elas alguém poderia considerar que fosse possível estando no estado 3 continuar a leitura de E sem tirar um símbolo do alfabeto da pilha A ausência das transições 3 x λ 3 λ e 3 y λ 3 λ impedem isso Assim quando o símbolo reaparece no topo da pilha terão sido lidos tantos ys quanto foram lidos xs anteriormente Ou seja o AP reconhece a linguagem L xnyn n ℕ uma linguagem que não era aceita por AFs Note que desde que o estado inicial é também um estado de aceitação a máquina aceita também a string x0y0 que é a sequência vazia λ Autômatos de Pilha como aceitadores de linguagem No exemplo anterior supomos que a string a ser analisada foi colocada em uma fita de entrada com o cabeçote de leitura da fita da máquina sobre a célula mais à esquerda da fita Supomos que a máquina inicia de seu estado inicial com uma pilha vazia e declara a string como aceita se for possível chegar a um estado de aceitação depois de ter lido toda a cadeia Isso deve acontecer em todo AP mas isso não significa necessariamente que a máquina deva encontrarse em um estado de aceitação imediatamente após ter lido o último símbolo da cadeia de entrada Ainda que a entrada já tenha sido toda lida a máquina ainda pode executar transições lendo ou não símbolos na pilha Ou seja depois de ler o último símbolo da entrada pode haver transições do tipo p λ x q y onde x e y podem ser o símbolo vazio λ Transições nessa situação farão com que a sequência de entrada seja aceita somente se um primeiro estado de aceitação a F seja alcançado mesmo que a pilha ainda contenha símbolos Por exemplo o autômato de pilha do diagrama na Figura 22 aceitaria a linguagem xmyn m n N e m n mas essas cadeias com mais xs que ys seriam aceitas tendo xs ainda na pilha Note que o autômato não pode aceitar cadeias com mais ys do que xs porque não seria capaz de ler todos os símbolos de uma tal string TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 727 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Figura 22 Repare que os APs que estamos apresentando aqui são nãodeterminísticos por exemplo pode haver uma transição p x y q z1 e uma transição p x y r z2 onde x e y podem ser λ e q r 2 A linguagem reconhecida pela autômato de pilha M é denotada por LM Ressaltamos que a linguagem LM é o conjunto de todas as strings aceitas por M Por exemplo seja M1 o autômato de pilha tal que L M1 an bm n m ℕ e m n A linguagem L M1 é o conjunto de todas as strings com uma sequência inicial de 0 ou mais as seguida de uma sequência de bs em número maior ou igual do que a sequência inicial de as Agora seja M2 o autômato de pilha tal que L M2 an bn n ℕ A linguagem L M2 é o conjunto de todas as strings com uma sequência inicial de 0 ou mais as seguida de uma sequência de bs em número igual à da sequência inicial de as Obviamente L M2 L M1 Ou seja toda sequência que M2 aceita será aceita também por M1 Mas M1 é uma máquina que não pode simular M2 As linguagens aceitas por APs incluem as linguagens regulares Isso é fácil de verificar Basta trabalhar com máquinas que restringem as transições disponíveis para APs àquelas na forma p x λ q λ ignorando o fato de que a máquina tem uma pilha Nesse caso as ações do AP dependem apenas do estado e do símbolo de entrada correntes Autômatos de Pilha que terminam com pilha vazia Podese conjecturar que a aplicação de uma teoria baseada em APs poderia facilmente levar a módulos de programa que retornam controle para outros módulos deixando restos de sua computação na pilha Estes lixo residual pode confundir as computações futuras Por esta razão é preferível considerar apenas APs que esvaziam suas pilhas antes de atingir um estado de aceitação Podemos ver pelo Teorema 21 que essa restrição não reduz o potencial das máquinas sendo consideradas 2 Infelizmente o nome AP não torna clara a natureza nãodeterminística deles Tecnicamente eles devem ser chamados APs nãodeterminísticos TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 827 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Teorema 21 Para cada AP que aceita cadeias sem esvaziar a sua pilha há um AP que aceita a mesma linguagem mas esvazia sua pilha antes de atingir um estado de aceitação Prova Suponha que M S Σ Γ T 𝔦𝔦 F é um AP que aceita cadeias sem necessariamente esvaziar sua pilha Vamos construir um autômato de pilha W Z Σ Δ D j G que esvazia sua pilha antes de atingir um estado de aceitação e tal que L W L M Vamos construir W a partir de M da seguinte forma 1 Todo estado em S é estado em Z Ou seja S Z 2 O estado inicial i deixa de ser inicial em W 3 Um estado j é criado para ser o novo estado inicial em W 4 Toda transição em T é transição em D Ou seja T D 5 É criada uma transição j λ λ i que leva o estado inicial novo ao antigo colocando o símbolo antes começar a leitura e com a pilha vazia O símbolo não pode ser símbolo de Γ 6 Um estado p é criado e para cada estado a F a transição a λ λ p λ é incluída em D 7 Para cada símbolo de pilha x Γ crie a transição p λ x p λ onde p é o estado criado no passo anterior 8 Crie um estado q e uma transição p λ q λ onde p é o mesmo estado criado no passo 6 e é o símbolo utilizado na transição descrita no passo 5 do novo estado inicial para o antigo estado inicial 9 Faça G q onde q é o estado criado no passo 8 Repare que o passo 9 retira o status de estado de aceitação de todos os estados que pertencem à f no autômato M O AP W marca a parte inferior da pilha antes de realizar qualquer outra instrução Em seguida simula as transições da máquina original M até um estado em que essa máquina original teria declarado a entrada como aceita ou seja M teria chegado a um estado de aceitação a F ao final da leitura Neste ponto a máquina modificada W deslocase para o novo estado p esvazia sua pilha e em seguida deslocase para o seu estado de aceitação q durante a remoção do marcador de basedepilha Assim ambas as máquinas M e a modificada a partir de M a W aceitam as mesmas cadeias exceto que a versão modificada atinge seu estado de aceitação apenas quando a pilha está vazia fimprova TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 927 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte A Figura 23 mostra o resultado da aplicação da técnica de conversão com o diagrama na Figura 22 Um AP com base neste diagrama irá aceitar as mesmas cadeias que o original mas só pode aceitar uma string quando sua pilha estiver vazia Figura 23 TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1027 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Exercícios 1 Desenhe um AP M tal que LM xn ym xn m n ℕ 2 Que linguagem é aceita pelo autômato com pilha cujo diagrama de transição é mostrado abaixo Solução A sequência vazia e qualquer string começada com uma subsequência de um ou mais xs intercalada por subsequências de ys tal que para a i ésima subsequência de ys Yi seu comprimento Yi é menor ou igual à diferença entre o total de xs e ys anteriores i 1 2 n sendo n o número de subsequências de ys Ou seja 3 Modifique o diagrama de transição no Exercício 2 para que o autômato com pilha associado aceite o mesmo conjunto de strings mas esvaziando sua pilha Solução Faça o algoritmo de 9 passos mostrado na prova do Teorema 1 4 Mostre como dois APs M1 e M2 podem ser combinados para formar um único autômato com pilha que aceitasse a linguagem LM1 LM2 Solução Os autômatos de pilha não são determinísticos Então podemos fazer diagramas paralelos com um novo estado inicial j tendo uma transição para cada um dos dois estados iniciais anteriores i1 e i2 rotulada por λ λ λ TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1127 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte 22 GRAMÁTICAS LIVRES DE CONTEXTO Definição Para caracterizar as linguagens reconhecidas pelos APs introduzimos o conceito de gramática livre de contexto Diferentemente das gramáticas regulares estas gramáticas não têm restrições sobre a forma no lado direito das regras de reescrita mas ainda é necessário que o lado esquerdo de cada regra seja um único nãoterminal A gramática no Quadro 21 é uma gramática livre de contexto mas não é uma gramática regular Quadro 21 S zMNz M aMa M z N bNb N z N zzzaM Gramática livre de contexto que gera cadeias da forma zanzanbmzbmz onde m n ℕ A gramática é livre de contexto porque uma vez que o lado esquerdo de cada regra de reescrita pode conter apenas um único nãoterminal a regra pode ser aplicada independentemente do contexto em que o nãoterminal é encontrado Por exemplo considere que a b e d são terminais Uma regra de reescrita como aNb adb diz que o nãoterminal N só pode ser substituído pelo terminal d quando ele está cercado pelos terminais a e b3 Portanto esta regra exige um contexto para a aplicação e obviamente uma gramática com tal regra não é livre de contexto Gramáticas livres de contexto geram strings através de derivações assim como gramáticas regulares No entanto no caso de gramáticas livres de contexto podem surgir dúvidas a respeito de qual nãoterminal substituir em um passo particular na derivação Vamos examinar o exemplo da gramática Quadro 21 A string zazabzbz pode ser produzida pela gramática em pelo menos duas maneiras S zMNz zaMaNz zazaNz zazabNbz zazabzbz seguindo a orientação de sempre aplicar uma regra de reescrita ao nãoterminal mais à esquerda da string corrente Isso é chamado de derivação pela esquerda S zMNz zMbNbz zMbzbz zaMabzbz zazabzbz obtida pela aplicação de uma regra de reescrita sempre sobre o nãoterminal mais à direita método chamado de derivação pela direita 3 Dependendo então do contexto onde se encontra TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1227 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Estas são as principais formas canônicas de derivação Poderíamos utilizar uma regra de começar a derivação pela direita e depois pela esquerda e assim sucessivamente O ponto é que a ordem na qual as regras de reescrita são aplicadas não têm efeito na determinação de quais strings podem ser geradas a partir de uma gramática livre de contexto Isto fica claro se reconhecemos que se uma string pode ser gerada pela gramática então ela pode ser gerada por uma derivação pela esquerda Para ver isto considere a árvore de análise sintática parse tree associada com a derivação Uma árvore de análise síntática nada mais é do que uma árvore cujos nós representam os terminais e nãoterminais da gramática com o nó raiz sendo símbolo inicial da gramática e os filhos de cada nó sendo os símbolos que substituem estes nãoterminais na derivação Nenhum símbolo terminal pode ser um nó interior da árvore e nenhum símbolo nãoterminal pode ser uma folha A árvore de análise para zazabzbz usando a gramática Quadro 21 em qualquer das derivações anteriores é mostrado na Figura 24 As derivações que diferem somente na ordem em que as regras de reescrita são aplicadas terão a mesma árvore de análise sintática A ordem em que as regras são aplicadas reflete a ordem em que os ramos da árvore de análise sintática são construídos Uma derivação mais à esquerda corresponde à construção da árvore de análise obedecendo à regra tipo primeiro o ramo esquerdo Uma derivação mais à direita corresponde a uma construção primeiro o ramo direito No entanto a ordem em que os ramos são construídos não afeta a estrutura da árvore final uma vez que cada ramo é independente dos outros Como exemplo a flexibilidade permitida nas gramáticas livres de contexto prevê a construção de uma gramática que gera a linguagem xnyn n N através das regras de reescrita S xSye S λ Figura 24 TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1327 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Este exemplo combinado com o fato de que qualquer gramática regular é também uma gramática livre de contexto nos permite concluir que as gramáticas livres de contexto geram um conjunto maior de linguagens do que as gramáticas regulares Chamamos as linguagens geradas por gramáticas livres de contexto das linguagens livres de contexto Gramáticas Livres de Contexto e APs Apenas por conveniência nessa sessão vamos considerar transições que colocam mais do que um símbolo individual na pilha tais como p a s q xyz Nessa transição os símbolos z y e x nessa ordem devem ser colocados na pilha Assim depois de executar a transição o símbolo x estará no topo da pilha com y abaixo e z na parte inferior Uma boa forma de visualizar é pensar que a string xyz está sendo empurrada para o fundo de um tubo de ensaio Observe que permitir transições desta forma é apenas uma questão de conveniência de notação e não adiciona qualquer capacidade para a máquina Com efeito a transição com colocação múltipla p a s q xyz pode ser simulada pela sequência normal de transições p a s q1 z q1 λ λ q2 y e q2 λ λ q x onde q1 e q2 são estados adicionais que não são utilizados em outras sequências de transições Vamos mostrar que as linguagens geradas por gramáticas livres de contexto são exatamente as linguagens aceitas por APs Fazemos isso em duas etapas Pelo Teorema 22 vamos mostrar que para qualquer gramática livre de contexto g existe um autômato de pilha M tal que LM LG Pelo Teorema 23 vamos mostrar o inverso ou seja que para qualquer autômato de pilha M há uma gramática livre de contexto G tal que LG LM Os teoremas 22 e 23 indicam que temos duas caracterizações para as linguagens livres de contexto São tanto as linguagens aceitas pelos APs quanto as linguagens geradas por gramáticas livres de contexto TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1427 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Teorema 22 Para toda gramática livre de contexto g existe um AP M tal que LG LM Prova A prova é através da construção de um AP a partir de uma gramática livre de contexto Dada a gramática livre de contexto g construa um AP M da seguinte maneira 1 O alfabeto Σ de M será o conjunto dos símbolos terminais de G 2 O conjunto de símbolos de pilha Γ de M será composto pelos símbolos terminais e nãoterminais de G e de um símbolo especial que não aparece nas regras da gramática Por exemplo vamos dizer que o símbolo se encaixa nesta situação 3 O conjunto E de estados de M será 𝔦𝔦 p q f onde 𝔦𝔦 é o estado inicial e f o único estado de aceitação 4 O conjunto T de transições de M terá a transição 𝔦𝔦 λ λ p indicando que a primeira coisa que M deve fazer é colocar o símbolo no fundo da pilha vazia 5 A transição p λ λ q S onde S é o símbolo de início de g deve estar em T 6 Para cada regra de reescrita N ω de G onde ω é a string do lado direito da regra a transição q λ N q ω deve ser incluída em T Aqui usamos a nova convenção que permite que uma única transição pode colocar na pilha mais do que um símbolo Em particular ω pode ser uma string de zero ou mais símbolos incluindo terminais e nãoterminais 7 Para cada símbolo x do alfabeto de M introduza em T a transição q x x q λ 8 Introduza a transição q λ f λ O AP construído desta maneira vai analisar sua string de entrada primeiramente marcando o fundo da pilha com em seguida coloca o símbolo inicial S na pilha e entra no estado q A partir daí e até que o símbolo apareça como o topo da pilha o AP vai retirar um nãoterminal do topo da pilha e o substituirá pelo lado direito de uma regra aplicável ou irá retirar um terminal do topo da pilha enquanto lê o mesmo terminal a partir da entrada Quando o símbolo aparecer no topo da pilha o autômato se deslocará para o estado de aceitação f indicando que a entrada foi lida e é aceitável Note que a cadeia de símbolos que compõem o lado direito de uma regra de reescrita é colocado na pilha da direita para a esquerda Por exemplo se ω xN o não terminal mais à esquerda na cadeia será o primeiro a aparecer no topo da pilha por conseguinte será também o primeiro nãoterminal na pilha a ser substituído Consequentemente o autômato analisa sua entrada através da realização de uma derivação mais à esquerda de acordo com as regras de funcionamento da gramática em que se baseia Mas como vimos todas as cadeias geradas por uma gramática livre de contexto têm uma derivação mais à esquerda Assim o autômato aceita exatamente a mesma linguagem como gerada pela gramática fimprova TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1527 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Exemplo de criação de AP a partir de uma gramática livre de contexto Vamos considerar as etapas executadas pelo autômato com pilha descrito no diagrama de transição da Figura 25 que foi construído a partir da gramática livre de contexto do Quadro 21 cujas regras são repetidas aqui e que gera cadeias na forma zanzanbmzbmz onde m n ℕ S zMNz M aMa M z N bNb N z Figura 25 Para avaliar a cadeia zazabzbz a máquina começa da configuração representada na Figura 26a A partir desta configuração a máquina marca a parte inferior da pilha com o símbolo e deslocase para q enquanto coloca o nãoterminal S na pilha para chegar à configuração representada na Figura 26b Figura 26 A partir deste ponto a pilha é usada para manter uma descrição da estrutura que a máquina espera encontrar na parte restante do seu fluxo de entrada Assim o S atualmente na pilha indica que a máquina espera que os símbolos restantes na sua entrada constituem uma estrutura que pode ser gerada a partir do nãoterminal S No entanto uma vez que S não é um terminal a máquina não pode esperar encontrar S na entrada explicitamente e assim o nãoterminal deve ser substituído antes que a TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1627 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte máquina tente comparar sua pilha diretamente com o fluxo de entrada Isto na verdade é uma regra geral seguida pela máquina Sempre que o topo da pilha contém um não terminal este deve ser substituído com um equivalente com uma descrição mais detalhada da estrutura Este é o propósito das transições introduzidas pelas regras do tipo 5 na prova do Teorema 22 A execução de uma regra do tipo 5 substitui um nãoterminal no topo da pilha por uma descrição mais detalhada da estrutura de acordo com alguma regra de reescrita na gramática original Assim a máquina no nosso exemplo de execução prossegue com a transição q λ S q zMNz para chegar à configuração representada na Figura 26c Figura 26 continuação Agora o topo da pilha da máquina contém o terminal z e assim o topo da pilha pode ser comparado com a cadeia de entrada através da transição qzzq λ Após esta transição ser executada a pilha da máquina contém MNz e os símbolos restantes na cadeia de entrada são azabzbz como representado na Figura 26d Mais uma vez o topo da pilha contém um nãoterminal que a máquina deve substituir No entanto em contraste com a substituição anterior do nãoterminal S existem duas regras de reescrita que podem ser aplicadas para substituir o nãoterminal M O AP pode executar a transição q λ M q z que faria com que a máquina falhe nesta tentativa de aceitar a cadeia ou poderia executar q λ M q aMa que neste caso seria a escolha correta Este autômato com pilha é não determinístico e isso está dentro das normas Vamos assumir a opção correta já que o nosso objetivo é observar como a máquina poderia aceitar a string de entrada em questão Lembrese que uma string está na linguagem de uma máquina nãodeterminística caso haja uma escolha possível de decisões que levem a máquina a aceitar a string TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1727 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Depois de executar q λ M q aMa a máquina aparece como está na Fig 2e com o terminal a no topo da pilha Este terminal é então comparado com a sequência de entrada através da transição qaaq λ deixando a pilha contendo MaNz com os símbolos ainda zabzbz a serem lidos partir da cadeia de entrada como mostrado na Figura 26f Figura 26 continuação As atividades restantes da máquina estão resumidas no Quadro 22 A leitura do último símbolo de entrada faz com que apareça o marcador na pilha A transição q λ λ faz a transferência para o estado de aceitação f e que a entrada é declarada aceita Vamos agora nos preparar para o Teorema 23 Suponha que nos é dado um AP que só aceita cadeias com a sua pilha vazia Então a tarefa do AP é tentar passar de seu estado inicial a um estado de aceitação de tal forma que a sua pilha esteja na mesma condição de quando a computação começou Como o autômato realiza esse objetivo depende das transições disponíveis Se por exemplo 𝔦𝔦 é estado inicial da máquina e 𝔦𝔦 λ λ p é uma transição disponível então o autômato pode tentar atingir seus objetivos primeiramente executando esta transição Isto resultaria na máquina encontrandose no Conteúdo da Pilha Transição executada Entrada remanescente Quadro 22 TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1827 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte estado de p com o símbolo na sua pilha e portanto em seguida o objetivo da máquina seria moverse do estado p para um estado de aceitação enquanto remove o símbolo da sua pilha Em geral nós representamos uma meta por p x q onde p e q são estados e x é um símbolo da pilha da máquina Isto é p x q representa o desejo de moverse do estado p para o q de tal maneira que a primeira ação a tomar é retirar o símbolo x do topo da pilha Obviamente tal transição só será possível se existe uma transição que pressuponha essa retirada Um caso especial de meta é denotado por p λ q que representa o objetivo de se moverse do estado p para o q sem alteração sobre a pilha Um exemplo disto é o objetivo original de movendose a partir do estado inicial para um estado de aceitação como discutido acima Na verdade para cada estado de aceitação f o autômato tem um objetivo principal representado por 𝔦𝔦 λ f onde 𝔦𝔦 é estado inicial da máquina Então podemos mostrar que a linguagem aceita por APs são livres de contexto Teorema 23 Para cada AP M há uma gramática livre de contexto G tal que LM LG Prova Dado um AP M E Σ Γ T i f a nossa tarefa é produzir uma gramática G livre de contexto que gera a linguagem LM Como resultado do Teorema 21 podemos assumir que o AP M aceita apenas cadeias com sua pilha vazia Feita esta observação nós construímos G de tal forma que os nãoterminais representem os objetivos que podemos escrever de acordo com o que foi definido no preâmbulo deste teorema e as regras de reescrita de G representem refinamentos de grandes objetivos em termos dos menores Mais precisamente especificamos que 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 E e x Γ λ ou seja x pode ser λ ou um símbolo de pilha de M Deste modo mesmo que M seja um autômato pequeno G pode ter um número imenso de nãoterminais Os terminais de G são os símbolos no alfabeto Σ de M fimprova TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 1927 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Estamos agora preparados para criar a primeira coleção de regras de reescrita de G R1 Para cada estado de aceitação f de M introduza a regra de reescrita S 𝔦𝔦 λ f onde 𝔦𝔦 é o estado inicial de M A regra R1 garante que qualquer derivação utilizando essa gramática vai começar substituindo símbolo inicial da gramática com um dos objetivos maiores do autômato R2 Para cada estado p em M introduza a regra de reescrita p λ p λ A regra R2 reflete o fato de uma meta de passar de um estado para si próprio sem modificar a pilha pode ser desconsiderada Cada uma das regras de reescrita restantes em G é construída a partir de um processo de transição em M utilizando as regras de formação R3 ou o R4 abaixo R3 Para cada transição p x y q z em M y λ para cada r E ou seja para cada estado r de M introduza a regra de reescrita p y r x q z r As regras do formato R3 refletem o fato de o objetivo de passar de um estado p para um outro estado r enquanto y é removido da pilha pode ser tentado movendose de q para r utilizando o recurso dessa transição Depois de ler x na fita de entrada e trocando y por z na pilha tentamos o objetivo de mudar de estado q para estado r enquanto removemos z da pilha R4 Para cada transição da forma p x λ q z introduza as regras de reescrita da forma p w r x q z k k w r onde w é um símbolo de pilha ou λ e k e r pertencem a E k pode ser igual a r Quando w λ e k r p λ r x q z r r λ r que é simplesmente p λ r x q z r refletindo a regra de formação R3 para y λ TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 2027 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Regras de reescrita construídas a partir da regra de formação R4 refletem o fato de que a meta de se mover do estado p para o estado r enquanto remove w da pilha pode ser alcançado primeiramente movendose para o estado q enquanto lê x na entrada e colocando z na pilha usando a transição p x λ q z e então movendose do estado q para o estado r através de um estado intermediário k enquanto remove z e w da pilha Observe que as regras de reescrita construídos pelas regras de formação R1 a R4 formam uma gramática livre de contexto Resta mostrar que essa gramática gera a mesma linguagem que o autômato aceita Ou seja temos de mostrar que qualquer cadeia gerada pela gramática pode ser aceita pelo autômato e que qualquer cadeia aceita pelo autômato pode ser gerada pela gramática Demonstração suspensa Veja o restante da demonstração no Anexo 1 Exemplo de criação de gramática livre de contexto a partir de um AP Vamos dar um único exemplo Vai ficar claro que a realização por um humano da tarefa de construção de uma gramática livre de contexto para um AP da maneira formal é inexequível mesmo para pequenos autômatos Considere a tarefa de construir uma gramática livre de contexto que aceite a linguagem c bn c n ℕ aceita pelo AP da Figura 27 Figura 27 Nossa primeira observação é que existem numerosos nãoterminais na gramática resultante incluindo o símbolo de início S mais um não terminal da forma p x q para cada tripla p x q onde x é ou λ ou c Já que c é o único símbolo de pilha e p e q possivelmente iguais são estados na máquina Além disso existem numerosas regras de reescrita que podem ser formadas como mostrado nos Quadros 23 24 25 e 26 onde as regras são listadas juntamente com sua transição associada quando apropriado O AP da Figura 27 é definido por Σ c E f g h Γ E o estado inicial é o f T f c λ g c g b λ g λ g c c h λ F h TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 2127 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Quadro 23 R1 Para cada t F introduza a regra de reescrita S f λ t S f λ h R2 Para cada p E introduza a regra de reescrita p λ p λ f λ f λ g λ g λ h λ h λ R3 Para cada dupla p x y q z T r E com y λ introduza a regra de reescrita p y r x q z r f c λ g c e g b λ g λ não geram nada por R3 porque nestes caso y λ g c c h λ gera g c f c h λ f g c g c h λ g g c h c h λ h R4 Para cada tripla p x λ q z T k E r E w Γ λ introduza a regra p w r x q z k k w r Σ b c E f g h Γ c p x λ q z T k f g h r f g h w c λ Para cada transição serão 3 3 2 18 regras TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 2227 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Quadro 24 A transição f c λ g c gera f w c λ r f g h c g c k f g h k w r Quadro 24a Para w λ Para r f f λ f c g c f f λ f k f f λ f c g c g g λ f k g f λ f c g c h h λ f k h Para r g f λ g c g c f f λ g k f f λ g c g c g g λ g k g f λ g c g c h h λ g k h Para r h f λ h c g c f f λ h k f f λ h c g c g g λ h k g f λ h c g c h h λ h k h Para w c Para r f f c f c g c f f c f k f f c f c g c g g c f k g f c f c g c h h c f k h Para r g f c g c g c f f c g k f f c g c g c g g c g k g f c g c g c h h c g k h Para r h f c h c g c f f c h k f f c h c g c g g c h k g f c h c g c h h c h k h TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 2327 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Quadro 25 A transição g b λ g λ gera g w c λ r f g h b g λ k f g h k w r Quadro 25 a Para w λ Para r f g λ f b g λ f f λ f k f g λ f b g λ g g λ f k g g λ f b g λ h h λ f k h Para r g g λ g b g λ f f λ g k f g λ g b g λ g g λ g k g g λ g b g λ h h λ g k h Para r h g λ h b g λ f f λ h k f g λ h b g λ g g λ h k g g λ h b g λ h h λ h k h Para w c Para r f g c f b g λ f f c f k f g c f b g λ g g c f k g g c f b g λ h h c f k f Para r g g c g b g λ f f c g k f g c g b g λ g g c g k g g c g b g λ h h c g k h Para r h g λ h b g λ f f c h k f g λ h b g λ g g c h k g g c h b g λ h h c h k h TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 2427 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Quadro 26 A transição g c c h λ gera g w c λ r f g h c h λ k f g h k w r Quadro 26 a Para w λ Para r f g λ f c h c f f λ f k f g λ f c h c g g λ f k g g λ f c h c h h λ f k h Para r g g λ g c h c f f λ g k f g λ g c h c g g λ g k g f λ g c h c h h λ g k h Para r h g λ h c h c f f λ h k f g λ h c h c g g λ h k g g λ h c h c h h λ h k h Para w c Para r f g c f c h c f f c f k f g c f c h c g g c f k g g c f c h c h h c f k h Para r g g c g c h c f f c g k f g c g c h c g g c g k g f c g c h c h h c g k h Para r h g c h c h c f f c h k f g c h c h c g g c h k g g c h c h c h h c h k h TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 2527 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte Finalmente uma derivação pela esquerda da string cbbc é mostrada Quadro 27 Quadro 27 S f λ h c g c h h λ h cb g λ g g c h h λ h cb g c h h λ h cbb g λ g g c h h λ h cbb g c h h λ h cbbc h λ h h λ h cbbc h λ h cbbc Aqui vemos que as regras de reescrita associadas a transições que leem símbolos da entrada da máquina introduzem esses mesmos símbolos na sequência que está sendo derivada Assim uma vez que o processo de derivação removeu todos os nãoterminais os símbolos encontrados na cadeia restante são exatamente aqueles que teriam sido lidos pela computação correspondente dos APs TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 2627 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte ANEXO 1 Continuação da prova do Teorema 23 Teorema 23 Para cada AP M há uma gramática livre de contexto G tal que LM LG Prova Continuação da prova iniciada na seção relativa a este teorema Para aqueles que gostam das minúcias matemática As afirmativas do parágrafo anterior se confirmarão se provarmos o que se segue Um nãoterminal p α q de G onde α é λ ou um símbolo de pilha pode ser reescrito como uma string de terminais w pela aplicação de regras da gramática 1 se e somente se o AP M pode moverse de um estado p para um estado q ao longo de um caminho que resulte na remoção de α da pilha e na leitura da string w a partir da fita da máquina M 2 Vamos provar o lado somente se desta afirmação4 usando indução no número de passos necessários para reescrever p α q até obter w Se apenas um passo é necessário então p α q deve ser realmente p λ p uma vez que esta é a única forma de um nãoterminal poder ser reescrito como uma cadeia terminal em uma única etapa a regra de formação R1 Isso por sua vez significa que w deve ser λ Assim nossa afirmação é válida para este caso base uma vez que o autômato pode sempre passar de algum estado p para p enquanto não remove nada da pilha e não lê nada da sua fita Agora vamos supor como hipótese indutiva que para qualquer caso em que um não terminal representando algum objetivo pode ser reescrito como uma sequência de terminais em n ou menos etapas o caminho representando esta sequência no autômato está presente Como tese temos que provar que isto também acontece com sequências de n1 terminais que reescreve um nãoterminal na gramática Para isto suponha que p α q pode gerar a cadeia w de terminais em n 1 passos Observe que a primeira etapa deste processo deve ser a aplicação de uma regra de reescrita obtida por R3 ou R4 acima Suponhamos que x Σ α e β pertencem a Γ e w seja obtido a partir de R3 pela transição p x α r β O caso de R4 é apenas uma generalização ligeira deste caso 4 Se 1 então 2 TIN0119 Linguagens Formais e Autômatos Prof Alexandre Andreatta 2727 com tradução livre do livro de J Glenn Brookshear CAPÍTULO 2 1ª parte A primeira etapa do processo de reescrita aparece como p α q x r β q Isto significa que o resto do processo de reescrita converte r β q em uma string w1 onde w xw2 em apenas n passos Assim pela nossa hipótese de indução o autômato pode moverse do estado r para o estado q enquanto lê w1 na entrada enquanto remove finalmente β de sua pilha Ao preceder a computação com a transição p x α r β obtemos uma computação que começa no estado p e se move para o estado q ao ler a string w da fita e remover α da pilha Assim podemos concluir que a parte apenas se da tese é válida Consideremos agora a parte se da afirmação em itálico5 Novamente aplicamos indução mas desta vez no comprimento do caminho de p para q Se este caminho tem comprimento zero o caminho não requer transições e q deve ser igual a p Portanto uma única regra de reescrita p x p λ basta Em seguida assumimos que se o autômato pode moverse de qualquer estado r para um estado s ao longo de um caminho que consiste em não mais de n transições e cujo percurso resulta na sequência w sendo lida a partir da fita e α onde α é λ ou um símbolo de pilha sendo removido da pilha então existem regras de reescrita na gramática que permitem que p α q seja reescrito como w Considere um caminho de n 1 passos do estado p para q cujo percurso resulta na sequência w ser lida a partir da fita e α onde α é λ ou um símbolo da pilha sendo removida da pilha Suponhamos que o primeiro passo nesse caminho seja a execução da transição p x α t z onde α λ Em seguida a porção restante do caminho deve moverse do estado t para o estado q em apenas n transições e resultar na remoção de nada da pilha ao ler na fita a cadeia w1 onde w xw1 Por nossa hipótese de indução no entanto isso significa que deve haver regras de reescrita na gramática que permitem que t λ q seja reescrito como w1 Além disso a existência da transição p x α t z implica a existência da regra p α q x t λ q Assim o nãoterminal p α q pode ser reescrito como w aplicando primeiramente esta regra e então procedendo a reescrever t λ q como w1 Concluímos que ambas as porções se e apenas se de nossa proposição devem ser válidas e portanto a gramática livre de contexto construída a partir de R1 R2 R3 e R4 deve gerar a mesma linguagem que é aceita pelo AP M fimprova 5 Se 2 então 1