Os DCFLs estão fechados sob reversão?

De acordo com este gráfico , os DCFLs são fechados sob reversão.

No entanto, não estou convencido de que seja a prova intuitiva (invertendo as setas da máquina de estados finitos controladores e alternando entre empurrões e estalos), pois isso depende do não-determinismo na escolha da transição nula a ser tirada do estado inicial (uma vez que o novo estado inicial conteria uma transição nula para todos os antigos estados finais).

Isso tornaria o "PDA reverso" de um DPDA não determinístico sempre que houver mais de um único estado final no DPDA original.

Qual é a falácia no meu argumento? Ou existe outra maneira de provar isso?

formal-languages context-free closure-properties pushdown-automata nondeterminism peteykun
fonte

Informe-me se minha resposta do StackOverflow exigir alguma explicação adicional. O problema com sua tentativa de prova é o seguinte: o PDA que você constrói não é o único PDA para o idioma que ele aceita. Pode haver outros, possivelmente chegados de maneira diferente, que são determinísticos. Em particular, os DCFLs podem ser aceitos por PDAs que não são determinísticos.

precisa saber é o seguinte

Certo, e é por isso que eu percebo que isso não é muito uma "prova", só teria sentido se o resultado fosse sempre um DCFL, o que não é. Eu acho que estava apenas tentando provar usando o mesmo método usado para idiomas regulares e falhou. Obrigado pelo exemplo contrário!

precisa saber é o seguinte

Considerar

L = b^{n} c^{n} \cap a b^{2} n c^{n}

$L={b^n c^n} \cap {a b^2n c^n}$

Pranav

Essa tabela também diz que os idiomas recursivos estão fechados

λ

$\lambda$ substituição gratuita ... está correto?

Anir 25/12

Respostas:

Procurei Hopcroft e Ullman 1979 e dizia na página 281 que não está fechado sob reversão. Mas não encontrei nenhuma prova no meu rápido olhar para o capítulo relevante.

Pesquisando na web também fornece uma resposta negativa, com um exemplo contrário, no stackoverflow por um membro do CS (notação adaptada):

$(a+b+c)^*WcW^R$ , Onde $W \in (a+b)^+$ ; isso é não determinístico, porque você não sabe onde o $WcW$ pouco começa.

$W^RcW(a+b+c)^*$ , Onde $W \in (a+b)^+$ ; isso é determinístico porque você pode escrever um PDA determinístico para aceitar palíndromos simples do formulário $W^RcW$ e modifique o estado de aceitação para fazer um loop em si mesmo em qualquer um dos $a$ , $b$ e $c$ .

O truque aqui é que os PDAs precisam ler as entradas da esquerda para a direita.

babou
fonte

Isso é um absurdo. Patrick87 forneceu os exemplos, @Raphael fez metade do trabalho de edição e eu recebo o representante. Então, temos tão pouco para o trabalho real ... :)

babou

Pense nisso como uma "taxa de localização" :) Estou apenas confuso que o sistema realmente funcione o suficiente para que você tenha encontrado aquele meu antigo posto. O sistema funciona! Salve SE!

precisa saber é o seguinte

A H&U ignorou a reversão da DCFL? Eles mencionam o não fechamento sob união, concatenação, Kleene, morfismo em Thm 10.5, ver Exercício 10.4 (com estrela, mas com uma solução). No entanto, eles observam

{0^{i} 1^{i} 2^{j} ∣ i, j} \cup {0^{i} 1^{j} 2^{j} ∣ i, j}

$\{ 0^i1^i2^j\mid i,j\} \cup \{ 0^i1^j2^j\mid i,j\}$ não é DCFL, então também não

K = {0^{i} 1^{i} 2^{j} a ∣ i, j} \cup {0^{i} 1^{j} 2^{j} b ∣ i, j}

$K = \{ 0^i1^i2^ja \mid i,j\} \cup \{ 0^i1^j2^jb\mid i,j\}$ pelo fechamento do DCFL sob quociente com conjunto regular, Thm 10.2. Mas a reversão de

K

$K$ é um DCFL, os 'marcadores'

a

$a$ e

b

$b$ forneça as informações onde usar o pushdown. [Talvez @babou possa adicionar isso se quiser; ele é quem coleciona os representantes aqui :)]

Hendrik Jan