Autómatos de Pilha

Um modelo computacional simples com memória ilimitada.

• Autómatos de Pilha
  • Introdução
  • Autómatos de Pilha e Gramáticas Independentes de Contexto
    • Diagramas de AP
    • Árvore das Computações
    • Variantes de AP
    • GIC e AP
    • Hierarquia de Chomsky
  • Conclusão

Introdução

Embora as GIC pareçam um candidato razoável para descrever as linguagens de programação, falta tratar as questões da computação: Como responder algoritmicamente, de forma eficiente, à questão $p\in L\left(G\right)$?

Intuitivamente, nos AFD e AFND a "memória" está representada pelos estados e portanto é limitada à priori, independentemente da palavra que vai ser processada. Por isso é que a linguagem $E=\left\{a^m{b}^m:m\ge 0\right\}$ "escapa" ao reconhecimento pelos AFD e AFND — "é preciso memorizar quantos $a$ foram lidos" e esse número é arbitrariamente grande.

As "pilhas" são uma forma simples de "memória ilimitada". Numa pilha podem ser colocados e retirados símbolos no "topo". A transição depende não só do estado e do símbolo da palavra mas também do símbolo que está no topo da pilha.

Autómatos de Pilha e Gramáticas Independentes de Contexto

Tal como foi feito para os AFD e AFND, depois da definição de autómato segue-se a configuração e computação e palavra aceite e linguagem reconhecida.

Autómato de Pilha (AP). Um Autómato de Pilha (AP) é um tuplo $A=\left(Q,\Sigma ,\Gamma ,\delta ,q_I,F\right)$ em que:

• Estados de Controlo, Alfabeto de Entrada, Estado Inicial, Estados Finais $Q,\Sigma ,q_I,F$ são como nos AFD.
• Alfabeto da Pilha $\Gamma$ é um conjunto finito de símbolos.
• Transição $\delta$ é uma função com assinatura

$$\delta :Q\times \left(\Sigma \cup \left\{\lambda \right\}\right)\times \left(\Gamma \cup \left\{\lambda \right\}\right)\to \mathcal{P}\left(Q\times \left(\Gamma \cup \left\{\lambda \right\}\right)\right)$$

Importa notar o seguinte:

A transição depende do estado de controlo, do símbolo de entrada e do símbolo no "topo" da pilha e define o novo estado de controlo e o novo símbolo no "topo" da pilha.

As computações dos AP são não deterministas, como resulta da assinatura da transição, na parte "$\mathcal{P}\left(\cdots \right)$". Formalmente:

Configuração. Computação. (AP). Seja $A=\left(Q,\Sigma ,\Gamma ,\delta ,q_I,F\right)$ um AP.

• Uma Configuração é um triplo $\left(i,p,\alpha \right)\in Q\times {\Sigma }^{\ast }\times {\Gamma }^{\ast }$.

• A Configuração Inicial para $p\in {\Sigma }^{\ast }$ é $\left(q_I,p,\lambda \right)$.

• Uma Computação é uma sequência de passos dos seguintes tipos:

  • AFND $\left(i,ap,\lambda \right)⊢\left(j,p,\lambda \right)$ se $\left(j,\lambda \right)\in \delta \left(i,a,\lambda \right)$ e $p\in {\Sigma }^{\ast }$.
  • Remove $\left(i,ap,A\alpha \right)⊢\left(j,p,\alpha \right)$ se $\left(j,\lambda \right)\in \delta \left(i,a,A\right)$ e $p\in {\Sigma }^{\ast }$.
  • Acrescenta $\left(i,ap,\alpha \right)⊢\left(j,p,A\alpha \right)$ se $\left(j,A\right)\in \delta \left(i,a,\lambda \right)$ e $p\in {\Sigma }^{\ast }$.
  • Troca $\left(i,ap,A\alpha \right)⊢\left(j,p,B\alpha \right)$ se $\left(j,B\right)\in \delta \left(i,a,A\right)$ e $p\in {\Sigma }^{\ast }$.

Informalmente, os tipos de passos de uma computação são

O critério de aceitação de uma palavra depende da configuração final.

Palavra Aceite. Linguagem Reconhecida. (AP) Seja $A=\left(Q,\Sigma ,\Gamma ,\delta ,q_I,F\right)$ um AP. A palavra $p\in {\Sigma }^{\ast }$ é aceite por $A$ se existe uma computação $$\left(q_I,p,\lambda \right)\stackrel{\ast }{⊢}\left(q,\lambda ,\lambda \right),q\in F.$$

A linguagem reconhecida (ou aceite) por $A$ é o conjunto das palavras aceites por $A$.

A condição $\left(q,\lambda ,\lambda \right),q\in F$ especifica que:

1. A computação chegou a um estado final,
2. Todos os símbolos de $p$ foram processados e
3. A pilha está vazia.

Além disso, a condição de aceitação depende de existir uma computação naquelas condições. Outras computações podem não ser assim. Portanto, para uma palavra ser rejeitada é necessário que nenhuma computação verifique todas.

Diagramas de AP

Os diagramas dos AP seguem as mesmas regras dos AFD e AFND, sendo apenas necessário indicar as operações na pilha.

Por exemplo, o AP por

• Estados de Controlo $Q=\left\{0,1\right\}$.
• Alfabeto de Entrada $\Sigma =\left\{a,b\right\}$.
• Alfabeto da Pilha $\Gamma =\left\{X\right\}$.
• Estado Inicial $q_I=0$.
• Estados Finais $F=\left\{1\right\}$.
• Transição

$$\begin{array}{ccccccc}q& a,\lambda & a,X& b,\lambda & b,X& \lambda ,\lambda & \lambda ,X\\ 0& 0,X& & & & 1,\lambda & \\ f1& & & & 1,\lambda & & \end{array}$$

tem o seguinte diagrama

Diagrama de AP para $\left\{a^m{b}^m:m\ge 0\right\}$

Note-se que na tabela da transição as colunas descrevem não só todas as possibilidades $\Sigma \times \Gamma$ como também os casos com $\lambda$.

Descrevendo os passos das computações por $$i,ap,A\alpha \stackrel{a,A/B}{⊢}j,p,B\alpha$$ algumas computações deste AP são:

1. De $\lambda$: $0,\lambda ,\lambda \stackrel{\lambda ,\lambda /\lambda }{⊢}1,\lambda ,\lambda$. Como $1$ é final e a entrada e a pilha estão vazias, $\lambda$ é aceite.
2. De $a$:
   1. $0,a,\lambda \stackrel{a,\lambda /X}{⊢}\boxed{0,\lambda ,X}\stackrel{\lambda ,\lambda /\lambda }{⊢}1,\lambda ,X$. Esta computação poderia ter parado em $\boxed{0,\lambda ,X}$, que não aceita $a$ tal como a última configuração.
   2. Em alternativa, $0,a,\lambda \stackrel{\lambda ,\lambda /\lambda }{⊢}1,a,\lambda$ que não aceita $a$.
   3. Como não há mais computações de $a$ esta palavra é rejeitada.
3. De $b$: $0,b,\lambda \stackrel{\lambda ,\lambda /\lambda }{⊢}1,b,\lambda$ é a única possibilidade e rejeita $b$.
4. De $ab$: $0,ab,\lambda \stackrel{a,\lambda /X}{⊢}0,b,X\stackrel{\lambda ,\lambda /\lambda }{⊢}1,b,X\stackrel{b,X/\lambda }{⊢}1,\lambda ,\lambda$ aceita.
5. De $ba$: é semelhante à computação de $b$.

A computação de $ab$ ilustra bem o uso da pilha como dispositivo de memória. Por cada $a$ lido da entrada é acrescentado uma "conta" $X$ à pilha. Quando se passa do estado $0$ para $1$ cada $b$ desconta a "conta" do topo. Se o número de $b$ for igual ao número de $a$ então no fim de processar todos os $b$ a pilha fica vazia.

Aquele AP tem mais "estrutura" do que apenas a contagem de $a$ e $b$. Por exemplo, $ba$ tem um $a$ e um $b$ mas é rejeitada devido à forma como o AP proíbe ler $a$ depois de começar a ler $b$.

Árvore das Computações

As computações dos AP, em geral, não são deterministas. Isto significa que, dada uma palavra para processar, o AP "gera uma árvore", em vez de uma única sequência.

Árvore das Computações. Seja $A=\left(Q,\Sigma ,\Gamma ,\delta ,q_I,F\right)$ um AP e $p\in {\Sigma }^{\ast }$. A árvore das computações de $p$ por $A$ é formada por:

• Raíz: A configuração $\left(q_I,p,\lambda \right)$.
• Filhos: Se $v$ for um vértice da árvore, para cada configuração $u$ tal que $v⊢u$ por $A$ então $u$ é um filho de $v$.

Por exemplo, no AP acima, a palavra $aabb$ tem a seguinte árvore de computação:

Árvore das Computações de $aabb$	Autómato de Pilha

Variantes de AP

O tipo de transições permitidas pela definição de AP é um caso intermédio entre:

• Autómato Atómico é um AP que só tem transições do tipo
  • $(j,\lambda )\in \delta \left(i,a,\lambda \right)$: AFND.
  • $(j,\lambda )\in \delta \left(i,\lambda ,A\right)$: Remove, mas não lê da entrada.
  • $(j,A)\in \delta \left(i,\lambda ,\lambda \right)$: Acrescenta, mas não lê da entrada.
• Autómato Estendido é um AP que também permite transições do tipo $(j,\beta \alpha )\in \delta \left(i,a,A\alpha \right)$ em que o topo da pilha é substituído por mais do que um símbolo ($A/\beta$).

Estas variantes são equivalentes, no sentido em que um AP de uma variante pode ser transformado num AP doutra.

GIC e AP

Os AP definem o aspeto computacional das CIG mas essa ligação ainda não foi definida:

Simulação de GIC por AP. Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC.

O AP $$A=\left(\left\{q\right\},\Sigma ,\Sigma \cup V,\delta ,q,\left\{q\right\}\right)$$ em que a transição é definida por

• Para cada variável $A\in V$,

$$\delta \left(q,\lambda ,A\right)=\left\{\left(q,p\right):A\to p\in P\right\}$$

• Para cada terminal $a\in \Sigma$,

$$\delta \left(q,a,a\right)=\left\{\left(q,\lambda \right)\right\}$$

é equivalente a $G$ no sentido em que $$L\left(G\right)=L\left(A\right)$$ se a pilha for iniciada com $S$.

Esta definição/transformação/teorema define como obter um AP equivalente a uma GIC dada. Embora o processo inverso fique fora do âmbito de ALP, para os efeitos pretendidos isto é suficiente.

Embora a condição sobre a inicialização da pilha contradiga a definição de AP, pode ser facilmente contornada. Basta definir um novo estado inicial $q_I$ e acrescentar a transição $\delta \left(q_I,\lambda ,\lambda \right)=\left\{\left(q,\lambda ,S\right)\right\}$.

Por exemplo, dada a GIC $S\to aSb|\lambda$ o AP equivalente é

AP da GIC $S\to aSb|\lambda$

As arestas associadas aos terminais e a cada variável são normalmente agrupadas de forma a facilitar a leitura do diagrama.

Este AP é equivalente ao anterior e à GIC da linguagem simplificada dos parêntesis equilibrados. Neste caso as produções da GIC podem ser "lidas" diretamente das arestas do AP.

Algumas computações deste AP:

1. De $\lambda$: $q_I,\lambda ,\lambda \stackrel{\lambda ,\lambda /S}{⊢}q,\lambda ,S\stackrel{\lambda ,S/\lambda }{⊢}q,\lambda ,\lambda$ aceita.
2. De $a$:
   1. $q_I,a,\lambda \stackrel{\lambda ,\lambda /S}{⊢}q,a,S\stackrel{\lambda ,S/\lambda }{⊢}q,a,\lambda$. não aceita.
   2. $q_I,a,\lambda \stackrel{\lambda ,\lambda /S}{⊢}q,a,S\stackrel{\lambda ,S/aSb}{⊢}q,a,aSb\stackrel{a,a/\lambda }{⊢}q,\lambda ,Sb\stackrel{\lambda ,S/\lambda }{⊢}q,\lambda ,b$. não aceita.
   3. $q_I,a,\lambda \stackrel{\lambda ,\lambda /S}{⊢}q,a,S\stackrel{\lambda ,S/aSb}{⊢}q,a,aSb\stackrel{a,a/\lambda }{⊢}q,\lambda ,Sb\stackrel{\lambda ,S/aSb}{⊢}q,\lambda ,aSbb$. não aceita.
   4. Não há mais computações de $a$, que é rejeitada.
3. De $ab$: $q_I,ab,\lambda \stackrel{\lambda ,\lambda /S}{⊢}q,ab,S\stackrel{\lambda ,S/aSb}{⊢}q,ab,aSb\stackrel{a,a/\lambda }{⊢}q,b,Sb\stackrel{\lambda ,S/\lambda }{⊢}q,b,b\stackrel{b,b/\lambda }{⊢}q,\lambda ,\lambda$ aceita.

A derivação de uma palavra na GIC é replicada na computação do AP.

Por exemplo, a palavra $ab$ tem a seguinte derivação: $$S\stackrel{S\to aSb}{\Rightarrow }aSb\stackrel{S\to \lambda }{\Rightarrow }ab$$ A mesma palavra tem a seguinte computação: $$q_I,ab,\lambda \stackrel{\lambda ,\lambda /S}{⊢}q,ab,S\stackrel{\boxed{\lambda ,S/aSb}}{⊢}q,ab,aSb\stackrel{a,a/\lambda }{⊢}q,b,Sb\stackrel{\boxed{\lambda ,S/\lambda }}{⊢}q,b,b\stackrel{b,b/\lambda }{⊢}q,\lambda ,\lambda$$

Hierarquia de Chomsky

As GIC não são o único tipo de gramática:

• Tipo 0 ou sem restrições as produções são da forma $p\to q$ em que $p\in {\left(V\cup \Sigma \right)}^{+}$ e $q\in {\left(V\cup \Sigma \right)}^{\ast }$. Isto é, o lado esquerdo pode ser qualquer palavra não vazia. A substituição de um símbolo depende da "vizinhança" desse símbolo, o seu contexto.
• Tipo 1 ou dependente de contexto são como as de tipo 0 mas $\left|p\right|\le \left|q\right|$. Tal como no Tipo 0 a substituição de símbolos depende do contexto mas, adicionalmente, as substituições contraem a palavra.
• Tipo 2 ou independente de contexto são as gramáticas usadas aqui. A substituição de um símbolo não depende do contexto em que este ocorre.
• Tipo 3 ou regular impõe ainda mais restrições às produções e geram as linguagens regulares.

Conclusão

Os AP são um modelo computacional das GIC. Especificamente, há um algoritmo que transforma uma GIC num AP equivalente. Além disso, as derivações na GIC são replicadas pelas computações do AP.

Ficam assim resolvidas as questões da adequação e da computação no Problema Principal de ALP — Dada uma linguagem $A$ e uma palavra $p$ no mesmo alfabeto, determinar se $p\in A$.

Falta ainda tratar da eficiência. Os AP não são deterministas e, ao contrário dos AFND, não se conhece nenhuma simulação determinista que seja geral e eficiente. A esperança que resta é condicionar as gramáticas de forma a que os AP associados sejam, em termos práticos, deterministas mas sem estragar a "capacidade expressiva" das gramáticas.

O próximo capítulo começa por visitar os principais tipos de Análise Sintática (o termo técnico do Principal Problema de ALP) e segue para métodos e tipos de gramáticas adequados à sua resolução eficiente.