3

Existe diferença de poder computacional entre um autômato com pilha determinístico e um não determinístico?

1 Resposta 1

8

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
  • 1
    @JeffersonQuesado, Cool (+1).
    – JJoao
    23/12/2017 às 14:32

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .