Dado un PDA M tal que L (M) está en DCFL, construya un DPDA N tal que L (N) = L (M)

¿Es posible construir un algoritmo que tome como entrada un autómata pushdown junto con la promesa de que el lenguaje aceptado por este autómata L ( M ) es un lenguaje determinista libre de contexto y genera un autómata determinista pushdown N que acepta exactamente el lenguaje aceptado por M ?$M$$L(M)$$N$$M$

Un problema equivalente sería construir un algoritmo que toma como entrada un pushdown autómatas (con la promesa de que L ( M ) es determinista, como arriba) y una autómatas de pila determinista N . La salida sería sí si L ( M ) = L ( N ) y no si L ( M ) ≠ L ( N ) .$M$$L(M)$$N$$L(M) = L(N)$$L(M)\neq L(N)$

Creo que un algoritmo que resuelve el primero daría un algoritmo que resuelve el segundo por la capacidad de decidir la equivalencia de los autómatas de empuje determinista. Creo que una solución para el segundo implicaría una solución para el primero, ya que enumeramos todos los autómatas de pushdown deterministas y ejecutamos el algoritmo uno por uno, una vez que obtenemos una instancia de sí, sacamos ese autómata.

Me pregunto si alguien sabe algo sobre esto. ¿Quizás es un problema conocido y / o tiene una solución conocida? Por otro lado, creo que es decidible si introduces la restricción que dice que el lenguaje generado por el PDA es el problema verbal de un grupo.

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

Pequeña aclaración:

Usted preguntó si el siguiente problema es decidible:

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

La respuesta es no, y de hecho se cumple el siguiente hecho más fuerte: El siguiente problema es indecidible:

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