Dado um PDA M tal que L (M) esteja no DCFL construa um DPDA N tal que L (N) = L (M)

É possível construir um algoritmo que tenha como entrada um autômato de empilhamento juntamente com a promessa de que a linguagem aceita por esse autômato L ( M ) é uma linguagem determinística livre de contexto e gera um autômato de empilhamento determinístico N que aceita precisamente a linguagem aceita por M ?$M$$L(M)$$N$$M$

Um problema equivalente seria construir um algoritmo que aceita como entrada um pushdown autómatos (com a promessa de que G ( M ) é determinista, como acima) e um autómatos pushdown determinista N . A saída seria sim se L ( M ) = L ( N ) e não se L ( M ) ≠ L ( N ) .$M$$L(M)$$N$$L(M) = L(N)$$L(M)\neq L(N)$

Acredito que um algoritmo que resolva o primeiro daria um algoritmo que resolva o segundo pela decidibilidade da equivalência de autômatos determinísticos de empilhamento. Penso que uma solução para a segunda implicaria uma solução para a primeira, pois enumeramos todos os autômatos de pushdown determinísticos e executamos o algoritmo neles um por um, uma vez que obtemos uma instância yes e produzimos esse autômato.

Gostaria de saber se alguém sabe alguma coisa sobre isso? Talvez seja um problema conhecido e / ou tenha uma solução conhecida? Como um aparte, acredito que é decidível se você introduzir a restrição que diz que o idioma gerado pelo PDA é o problema da palavra de um grupo.

$M$$w$$w$$L$$w$$L = A^{\ast}$$M$$w$$L = A^{\ast} - \{h\}$$h$$M$$w$$h$$L$$L$$L$

Pequenos esclarecimentos:

Você perguntou se o seguinte problema é decidível:

$M$$L(M)$$N$$L(M) = L(N)$

A resposta é não e, de fato, o seguinte fato mais forte é válido: O seguinte problema é indecidível:

$M$$L(M)$$L(M)=A^{\ast}$