Aula 12

Linguagens Independentes de Contexto (CFL)

Já sabemos que há linguagens que não são regulares. Que podemos fazer aos autómatos (DFA e NFA) por forma a que estes passem a ser mais expressivos, ou seja reconheçam mais linguagens?

Se munirmos os autómatos de memória genérica adicional ficamos imediatamente com uma expressividade que é muito superior à que desejamos.

A solução é a de dotar os autómatos de uma estrutura de pilha (um stack).

Uma pilha (que em geral não tem profundidade máxima) podemos fazer somente três operações:

• TOP(\(\ell\)) que verifica se o a célula do topo da pilha contém o símbolo \(\ell\). O resultado é, portanto, booleano;

• POP que apaga a célula de topo da pilha;

• PUSH[\(x\)) que coloca o símbolo x no topo da pilha, tendo previamente “empurrado” todas as células desta para a posição imediatamente mais abaixo do que a que estava.

Autómatos de pilha (PDA)

Definição

Um autómato de pilha (PDA) \(A\) é um tuplo ordenado \[\langle Q,\Sigma, \Gamma, \delta, I, z_0, F\rangle,\] com

• \(Q\) é o conjunto (finito) de estados do autómato,

• \(\Sigma\) é o alfabeto da linguagem de input,

• \(\Gamma\) é o alfabeto usado na pilha,

• \(\delta\) é a função de transições, com \[\delta:Q\times(\Sigma\cup\{\varepsilon\})\times \Gamma\longmapsto 2^{Q\times \Gamma^\star}\]

• \(q_0\subseteq Q\) é o estado inicial,

• \(z_0\in\Gamma\) é o símbolo inicial que reside sozinho, inicialmente, na pilha,

• \(F\subseteq Q\) é o conjunto dos estados finais.

Em cada momento, o autómato procede, supondo que se encontra no estado \(q\), e se \[\delta(q,\sigma,\gamma)\ni(q',w),\] com \(q,q'\in Q, \sigma\in\Sigma, \gamma\in\Gamma, w\in\Gamma^\star\), se o caracter que se encontra sob a cabeça de input do autómato é \(\sigma\) e o símbolo que se lê na posição de topo da pilha é \(\gamma\),

• move a cabeça de leitura de input uma posição para a direita;

• muda para o estado \(q'\);

• apaga a célula de topo da pilha (POP);

• coloca, por ordem, cada um dos símbolos de \(w\) (PUSH), forçando que cada uma das células já presentes na pilha sejam movidas para a posição imediatamente seguinte.

Se \[\delta(q,\varepsilon,\gamma)\ni(q',w),\] independentemente do símbolo que se encontra sob a cabeça de leitura de input do autómato, e se o valor que se encontra na célula de topo da pilha é \(\gamma\),

• não move a cabeça de leitura de input;

• muda para o estado \(q'\)

• apaga a célula de topo da pilha (POP);

• coloca, por ordem, cada um dos símbolos de \(w\) (PUSH), forçando que cada uma das células já presentes na pilha sejam movidas para a posição imediatamente seguinte.

Em qualquer momento da execução do PDA \(A\), podemos descrever a sua configuração pela seguinte palavra de \(\Gamma^\star\times Q\times\Sigma^\star\): \[z_0p_1\cdots p_{\ell-1}p_\ell qi_mi_{m+1}\cdots i_{n-1}\] em que

• \(q\) é o estado corrente do autómato,

• \(i_mi_{m+1}\cdots i_{n-1}\) é o que resta do input para ser lido, sendo que a cabeça de leitura do input está sobre \(i_m\),

• \(z_0p_1\cdots p_{\ell-1}p_\ell\) é o conteúdo da pilha sendo \(p_{\ell}\) o conteúdo da célula de topo da pilha.

Então, a configuração inicial de \(A\) para o input \(w=\sigma_0\sigma_1\cdots\sigma_{n-1}\), será \[z_0q_0\sigma_0\sigma_1\cdots\sigma_{n-1}.\] Podemos descrever a evolução de \(A\) durante a avaliação de um input da seguinte forma: \[(vpq\sigma u)\Rightarrow (vwq'u),\] sendo \(u\in\Sigma^\star\) e \(v,w\in\Gamma^\star\), se \(\delta(q,\sigma,p)\ni(q',w)\), e \[(vpqu)\Rightarrow_A (vwq'u),\] sendo \(u\in\Sigma^\star\) e \(v,w\in\Gamma^\star\), se \(\delta(q,\varepsilon,p)\ni(q',w)\).

Definição

Seja \(A=\langle Q,\Sigma,\Gamma,\delta,q_0,z_0,F\rangle\) um autómato de pilha. A linguagem definida por \(A\) é o conjunto de palavras para as quais há uma sequência de configurações, de acordo com \(\delta\), que começa com uma configuração inicial e termine uma configuração de aceitação. Uma configuração inicial tendo como input a palavra \(w\in\Sigma^\star\) é uma configuração \(z_0q_0w\), com \(q_0\). Uma configuração de aceitação é uma configuração \(\alpha q_f\) com \(q_f\in F\) e \(\alpha\in\Gamma^\star\). Portanto a palavra \(w\in\mathcal{L}(A)\) se existir \[z_0q_0w \Rightarrow^\star \alpha q_f,\] com \(q_f\in F\) e \(\alpha\in\Gamma^\star\).

Exemplo:

Consideremos a linguagem \(L=\{a^nb^n\mid n\in\mathbb{N}\}\). O seguinte autómato de pilha (PDA) \(A\)

Consideremos a evolução de \(A\), com input \(aaabbb\): \[\begin{gathered} Zq_0aaabbb \Rightarrow ZAq_1aabbb \Rightarrow ZAAq_1abbb \Rightarrow ZAAAq_1bbb\Rightarrow\\ ZAAq_2bb \Rightarrow ZAq_2b \Rightarrow Zq_2 \Rightarrow Zq_3, \end{gathered}\] portanto, a palavra \(aaabbb\) é aceite pelo autómato. Com o input \(aabbb\) como não há evolução de \(A\) que, com input dessa palavra, partindo de \(Zq_0aabbb\) chegue a uma configuração com estado \(q_0\) ou \(q_3\) e que consuma todo o input. Portanto \(aabbb\notin\mathcal{L}(A)\).

Exemplo:

Para a linguagem \(\{w\mid w\in \{a,b\}^\star, |w|_a=|w|_b\}\) podemos considerar o seguinte autómato de pilha:

Para a palavra \(abbaab\) temos a seguinte sucessão de configurações: \[\begin{gathered} Zq_0abbaab\Rightarrow ZAq_0bbaab \Rightarrow Zq_0baab\Rightarrow ZBq_0aab\Rightarrow\\ Zq_0ab\Rightarrow ZAq_0b\Rightarrow Zq_0\Rightarrow Zq_1. \end{gathered}\] Portanto a palavra é aceite pelo autómato.