CCT-UFCA/Ciência da Computação/Autômatos e Linguagens Formais/Equivalencia entre GLCs e Aps

Teorema: Uma linguagem é livre de contexto se e somente se algum autômato com pilha a reconhece.

Ida

Se uma linguagem é livre de contexto, então existe um AP que a reconhece.

Ideia: Seja A uma LLC. Da definição sabemos que A tem uma GLC, G, que a gera. Mostramos como converter G em um AP equivalente, que chamamos P.

O AP P que agora descrevemos funcionará aceitando sua entrada w, se G gera aquela entrada, determinando se existe uma derivação para w. Lembre-se que uma derivação é simplesmente a sequência de substituições feitas à medida que a gramática gera uma cadeia. Cada passo da derivação dá origem a uma cadeia intermediária de variáveis e terminais. Projetamos P para determinar se alguma série de substituições usando as regras de G podem levar da variável inicial para w.

Uma das dificuldades em se testar se existe uma derivação para w está em descobrir quais substituições fazer. O não-determinismo do AP o permite estipular a sequência de substituições corretas. A cada passo da derivação uma das regras para uma variável é selecionada não-deterministicamente e usada para substituir aquela variável.

O AP P começa escrevendo a variável inicial na sua pilha. Ela passa por uma série de cadeias intermediárias, fazendo uma substituição após outra. Em algum ponto ele pode chegar a uma cadeia que contém somente símbolos terminais, o que quer dizer que ele derivou uma cadeia usando a gramática. Então P aceita se essa cadeia for idêntica à cadeia que ela recebeu como entrada.

Implementar essa estratégia em um AP requer uma ideia adicional. Precisamos ver como o AP armazena as cadeias intermediárias à medida que ela vai de uma para outra. Simplesmente usar a pilha para armazenar cada cadeia intermediária é tentador. Entretanto, isso não chega a funcionar porque o AP precisa encontrar as variáveis na cadeia intermediária e fazer substituições. O AP pode acessar somente o símbolo no topo da pilha e esse pode ser um símbolo terminal ao invés de uma variável. A forma de contornar esse problema é manter somente parte da cadeia intermediária na pilha: os símbolos começando com a primeira variável na cadeia intermediária. Quaisquer símbolos terminais aparecendo antes da primeira variável são emparelhados imediatamente como símbolos na cadeia de entrada.

A seguir vai uma descrição informal de P.

1. Coloque o símbolo marcador $ e a variável inicial na pilha
2. Repita os seguintes passos para sempre.
   1. Se o topo da pilha é um símbolo de variável A, não-deterministicamente selecione uma das regras para A e substitua A pela cadeia no lado direito da regra.
   2. Se o topo da pilha é um símbolo terminal a, leia o próximo símbolo da entrada e compare-o com a. Se eles casam, repita. Caso contrário, rejeite nesse ramo do não-determinismo.
   3. Se o topo da pilha é o símbolo $, entre no estado de aceitação. Fazendo isso aceite a cadeia se ela foi toda lida.

Volta

Se um autômato com pilha reconhece uma dada linguagem, então ela é livre-de-contexto.

Ideia da prova: Temos um AP P, e desejamos construir uma GLC G que gera todas as cadeias que P aceita. Em outras palavras, G deve gerar uma cadeia se aquela cadeia faz o AP ir do seu estado inicial para um estado de aceitação.

Para atingir esse resultado projetamos uma gramática que faz algo mais. Para cada par de estados p e q em P a gramática terá uma variável A_pq. Essa variável gera todas as cadeias que pode levar P de p com uma pilha vazia a q com uma pilha vazia. Observe que tais cadeias podem também levar P de p para q, independente do conteúdo da pilha em p, deixando a pilha em q na mesma condição em que ela estava em p.

Primeiro, simplificamos nossa tarefa modificando P levemente para lhe dar as seguintes características.

1. Ele tem um único estado de aceitação, q_aceita.
2. Ele esvazia sua pilha antes de aceitar.
3. Cada transição ou empilha um símbolo na pilha (um movimento de empilhar) ou desempilha um da pilha (um movimento de desempilhar), mas não faz ambos ao mesmo tempo.

Dar a P as características 1 e 2 é fácil. Para lhe dar a característica 3, substituímos cada transição que simultaneamente desempilha e empilha com uma sequência de duas transições que passa por um novo estado, e substituímos cada transição que nem empilha nem desempilha por uma sequência de duas transições que empilha e depois desempilha um símbolo de pilha arbitrário.

Para projetar G de modo que A_pq gere todas as cadeias que levam P de p para q, começando e terminando com uma pilha vazia, temos que entender como P opera sobre essas cadeias. Para cada tal cadeia x, o primeiro movimento de P sobre x tem que ser um empilha, pois todo movimento é um empilha ou um desempilha e P não pode desempilhar uma pilha vazia. Igualmente o último movimento sobre x tem que ser um desempilha, pois a pilha termina vazia.

Duas possibilidades ocorrem durante a computação de P sobre x. Ou o símbolo desempilhado no final é o símbolo que foi empilhado no início, ou não. Se for, a pilha está vazia somente no início e no fim da computação de P sobre x. Se não for, o símbolo inicialmente empilhado tem que ser empilhado em algum ponto antes do final de x e portanto a pilha se torna vazia nesse ponto. Simulamos a primeira possibilidade com a regra A_pq → aA_rsb onde a é o símbolo de entrada lido no primeiro movimento, b é o símbolo lido no último motivmento, r é o estado seguinte a p, e s o estado que precede q. Simulamos a segunda possibilidade com a regra A_pq → A_prA_rq, onde r é o estado no qual a pilha se torna vazia.