Existe diferença de poder computacional entre um autômato com pilha determinístico e um não determinístico?
1 Resposta
Sim, existe diferença entre os dois. E ela é brutal. Autômatos de pilha não-determinísticos conseguem resolver muito mais linguagens livres de contexto do que os determinísticos.
Gostaria de ressaltar que isso vai de encontro com outros autômatos, onde a Máquina de Turing não-determinística não provê poder computacional além daquele que a determinística consegue prover, assim como na Maquina de Estados Finita não-determinística pode ser transformada em determinística sem perda de poder computacional.
O conjunto de linguagens reconhecidas por autômatos de pilha determinísticos é um subconjunto próprio do conjunto de linguagens reconhecidas por autômatos de pilha não-determinísticos.
Por exemplo, a linguagem composta por todo parêntese precisa ser fechado em ordem de abertura é determinística. Por exemplo, usando apenas parênteses curvos e quadrados, a gramática seria:
S --> '(' S ')'
S --> '[' S ']'
S --> '(' ')'
S --> '[' ']'
Agora, para palíndromos, isso não acontece. Pegue um palíndromo simples, composto apenas por a
e b
:
S --> 'a' S 'a'
S --> 'b' S 'b'
S --> 'a' 'a'
S --> 'b' 'b'
S --> 'a'
S --> 'b'
Como é que o autômato consegue distinguir se ele deve considerar um terminal a
como sendo o começo da criação de um par ou o final? Por exemplo, as seguintes palavras são ambíguas:
aabaa
aabababaa
É impossível para um autômato de pilha determinístico determinar se o a
depois do b
deve ser para começar um novo par ou se ele casa com o a
anterior.
-
1