CCT-UFCA/Ciência da Computação/Autômatos e Linguagens Formais/Autômatos de Pilha Determinísticos

Autômatos com pilha determinísticos (APD) são uma classe fundamental de máquinas teóricas na teoria da computação e na linguística formal, utilizados para modelar e analisar linguagens que exigem um controle mais definido do que o que é possível com autômatos com pilha tradicionais (não-determinísticos). O determinismo de um APD proporciona uma maneira de lidar com as cadeias que é crucial para reconhecer linguagens que possuem dependências aninhadas ou recursivas, como as linguagens de programação e as expressões matemáticas, de forma determinística.

Os autômatos com pilha determinísticos operam de acordo com um conjunto bem definido de regras, e, ao contrário de seus equivalentes não-determinísticos, suas transições de estado são sempre unicamente determinadas pelo estado atual, pelo símbolo a ser lido e pelo símbolo no topo da pilha, garantindo um comportamento previsível e eficiente. Eles são capazes de reconhecer exatamente as linguagens livres-de-contexto determinísticas, que incluem uma ampla gama de linguagens utilizadas em várias áreas da ciência da computação e que detalharemos mais a frente.

Compreender os autômatos com pilha determinísticos é essencial para a análise e processamento de linguagens formais, oferecendo uma base sólida para a construção de compiladores, interpretadores e outras ferramentas de processamento de linguagem que são vitais para o desenvolvimento de software e a análise de sistemas complexos.

Definição formal e Funcionamento das APDs

Observação: Se Σ é um alfabeto, Σ_ε denota o conjunto Σ ∪ {ε};

Formalmente, um APD é uma tupla M = (Q, Σ, Γ, δ, q₀, F), onde:

Q é o conjunto finito de estados;
Σ é o alfabeto de entrada;
Γ é o alfabeto da pilha;
δ : Q × Σ_ε × Γ_ε → P(Q × Γ_ε) é a função de transição possuindo as seguintes restrições:
- para cada q ∈ Q, a ∈ Σ_ε e x ∈ Γ_ε, o conjunto δ(q,a,x) tem no máximo 1 elemento;
- para cada q ∈ Q e x ∈ Γ_ε, se existe um símbolo a ∈ Σ tal que o conjunto δ(q, a, x) tem 1 elemento, então δ(q, ε, x) é vazio;
- para cada q ∈ Q e a ∈ Σ_ε, se existe um símbolo x ∈ Γ tal que o conjunto δ(q, a, x) tem 1 elemento, então δ(q, a, ε) é vazio;
q₀ é o estado inicial, onde q₀ ∈ Q;
F ⊆ Q é o conjunto de estados de aceitação.

De fato, por essa definição, todo APD é também um AP, porém nem todo AP é um APD.

O funcionamento de um APD é baseado em transições determinísticas, o que significa que, para cada combinação de estado atual, símbolo de entrada e símbolo no topo da pilha, a função de transição δ especifica de maneira única o próximo estado e a sequência de operações na pilha. Assim, não há ambiguidade no comportamento do autômato, ou seja, para cada situação possível, existe uma única ação a ser tomada.

Quando o autômato processa uma cadeia de entrada, ele começa no estado inicial q₀ e com a pilha vazia. Em cada passo, o autômato lê um símbolo da entrada e o símbolo no topo da pilha, consulta a função de transição para determinar o próximo estado e a operação da pilha a ser executada, e então realiza essas operações. A pilha pode ser manipulada de várias maneiras: empilhando novos símbolos, desempilhando o topo atual, ou substituindo o topo da pilha por uma nova sequência de símbolos. Um autômato com pilha determinístico aceita uma cadeia de entrada se, após processar toda a cadeia, ela se encontra em um estado final.

Propriedades das APDs

Uma linguagem livre-de-contexto determinística (LLCD) é uma linguagem que pode ser reconhecida por um APD. Exemplos de LLCD são as linguagens L₁ = {0ⁿ1ⁿ2^m | n, m ≥ 0} sobre o alfabeto Σ₁ = {0, 1, 2} e L₂ = {w#w⁻¹ | w ∈ {0, 1}*} sobre o alfabeto Σ₂ = {0, 1, #}.

Teorema 1. As linguagens L₁ = {0ⁿ1ⁿ | n ≥ 0} sobre o alfabeto Σ₁ = {0, 1}; L₂ = {w#w⁻¹ | w ∈ {0, 1}*} sobre o alfabeto Σ₂ = {0, 1, #} e L₃ = {0ⁿ#0^m | 0 ≤ n ≤ m} sobre o alfabeto Σ₃ = {0, #} são LLCDs.

Demonstração. O seguinte APD reconhece a linguagem L₁:

O seguinte APD reconhece a linguagem L₂_:

Finalmente, o seguinte APD reconhece a linguagem L₃_:

Toda linguagem regular também é uma LLCD, visto que um AFD pode ser visto como um APD que não faz uso da sua pilha. Portanto, como as linguagens do Teorema 1 não são regulares, temos que os APDs possuem um poder de expressão maior do que os AFDs e AFNs.

Como todo APD é também um AP, temos que toda LLCD é também uma linguagem livrede-contexto. No entanto, temos que há linguagens livres-de-contexto que não são LLCDs, por exemplo, a linguagem sobre o alfabeto Σ = {0, 1} que contém todos os palíndromos com tamanho par. A intuição de que ela não é uma LLCD vem do fato de que uma APD não tem como decidir com certeza se a cadeia de entrada já foi lida até a sua metade ou não, e, por isso, é necessário o uso de não-determinismo nesse ponto.

Com isso temos que os APs possuem um poder de expressão maior do que os APDs, dado que a linguagem do palíndromos de tamanho par sobre o alfabeto Σ = {0, 1} é livre-decontexto, porém não é uma LLCD. Com isso, concluímos que o conjunto das linguagens regulares está estritamente incluído dentro do conjunto das LLCDs, que, por sua vez, está estritamente incluída dentro do conjunto das linguagens livres-de-contexto. Na Figura 1, temos um diagrama ilustrando a hierarquia dessas classes de linguagens no contexto de inclusão.

Sobre as propriedades de fecho das LLCDs, o conjunto das LLCDs é fechado em relação ao complemento, ou seja, o complemento de uma LLCD é também uma LLCD. Por outro lado, o conjunto das LLCDs não é fechado para a união, a interseção, a concatenação e a operação estrela. Por exemplo, as linguagens L₁ = {0ⁿ1ⁿ2^m | n, m ≥ 0} e L₂ = {0^m1ⁿ2ⁿ | n, m ≥ 0} são ambas LLCDs, porém a sua interseção L₁ ∩ L₂ = {0ⁿ1ⁿ2ⁿ | n ≥ 0} não é (ela sequer é livre-de-contexto). No entanto, se L₁ é uma LLCD e L₂ é uma linguagem regular, a sua união, interseção e concatenação são LLCDs.

Outra propriedade interessante e relevante em áreas como a construção de compiladores é a de que toda LLCD é gerada por alguma gramática livre-de-contexto não-ambígua, característica essa essencial para linguagens formais que descrevem a sintaxe de linguagens de programação. De fato, toda linguagem reconhecida por um APD que possui apenas um estado é uma linguagem LL(1), que é uma classe de linguagens importantes na representação sintática de linguagens de programação por possuí parsers eficientes.

Linguagens não-LCD

Para mostrar que uma linguagem não é livre-de-contexto determinística, existe um Lema do Bombeamento para LLCDs [1]. No entanto, ao contrário dos lemas do bombeamento das linguagens regulares e livres-de-contexto, esse lema do bombeamento é complexo de se entender e de se aplicar.

Uma outra forma de se provar que uma linguagem não é livre-de-contexto determinística usando linguagens não livres-de-contexto. Essa abordagem, consiste em supor por absurdo que uma linguagem é LLCD e, usando o seu APD, construir um AP para uma linguagem que se sabe que não é LLC.

Para exemplificar essa abordagem, abaixo, provamos que a linguagem L = {aⁿb^m | m = n ou m = 2n} não é uma LLCD. Suponha por absurdo que ela é uma LLCD e seja M₁ o seu APD. Temos que, para cada n ≥ 0, as cadeias aⁿbⁿ e aⁿb²ⁿ são aceitas e, como o APD é determinístico, o caminho que o APD faz para aceitar a cadeia aⁿb²ⁿ deve passar pelo estado de aceitação que aceita a cadeia aⁿbⁿ, visto que aⁿbⁿ é prefixo de aⁿb²ⁿ. Esta situação está ilustrada abaixo.

Se mudarmos todo símbolo b por um c, temos um outro APD, digamos M₂, em que a mesma situação da figura acima se repete, mas para os símbolos a e c. Esta situação está ilustrada abaixo.

Considere o AP M construído da seguinte forma: adicione M₁ e M₂, fazendo o estado inicial de M₁ ser o estado inicial de M; faça os estados finais de M₁ e M₂ serem os estados finais de M e, para cada n, adicionarmos uma transição ε, ε → ε do estado de aceitação de M₁ que aceita aⁿbⁿ para o estado de aceitação de M₂ que aceita aⁿcⁿ e do estado de aceitação de M₁ que aceita aⁿb²ⁿ para o estado de aceitação de M₂ que aceita aⁿc²ⁿ. Essa construção está ilustrada abaixo.

Temos que toda cadeia aceita por M₁ é aceita por M. Adicionalmente, toda cadeia aⁿbⁿcⁿ também é aceita para todo n ≥ 0. Assim, temos que L(M) = L ∪ {aⁿbⁿcⁿ | n ≥ 0}, o que é um absurdo, pois é possível mostrar pelo lema do bombeamento, que L(M) não é uma LLC.

Referências

[1] Yu, S. A pumping lemma for deterministic context-free languages. Information Processing Letters, vol. 31 (1), p. 47-51. 1989.Disponível em: https://sci-hub.se/https://www.sciencedirect.com/science/article/abs/pii/0020019089901087. Acesso em: 11/11/2024.