¿Es posible minimizar los autómatas pushdown?

8

¿Es posible minimizar los autómatas pushdown? Si no, ¿por qué? ¿Es porque para minimizar las clases de equivalencia deben tener un índice finito y no podemos garantizarlo para CFG?

computability automata pushdown-automata Tom J.
fuente

Respuestas:

8

Lamentablemente, el problema no es computable. Es indecidible incluso decir si dos PDA arbitrarias son equivalentes; minimizar un PDA es aún más difícil.

DW
fuente
6

Respondí básicamente la misma pregunta (más generalmente) aquí .

El argumento en resumen: si pudiera hacer esto, podría decidir la universalidad y un par de otras propiedades indecidibles de PDA / CFG. Por lo tanto, por reducción, no puede existir tal minimizador.

Rafael
fuente
4

Lo sentimos, ¿minimizar en términos de qué?

Cada PDA tiene un equivalente que tiene un solo estado.

Hendrik Jan
fuente
Huh, cierto :) Supongo que "tamaño de una codificación razonable", por ejemplo, la tabla de transición. Las otras respuestas funcionarían con eso, ¿no?
Raphael
2

No sé acerca de minimizar en la forma en que lo haces con autómatas no pushdown, pero ...

Puede convertir un CFG a PDA ¿verdad? Y esa conversión según Hopcroft tiene solo un estado, que está muy minimizado, ¿no crees? Entonces, todo lo que tiene que hacer es convertir su PDA a CFG, y luego su CFG nuevamente a PDA, tendrá un PDA de 1 estado.

H_DANILO
fuente
Tenga en cuenta que esto es mínimo de estado, pero no mínimo de transición. Como dice DW, hacer que la transición y el estado sean mínimos es indiscutible.
jmite
0

"minimizar" generalmente significa "mínimo global", pero a veces puede referirse a un "mínimo local", en cuyo caso existen heurísticas, es decir, estrategias que pueden dar lugar a una reducción pero no encontrar consistentemente el mínimo global. y también algunas clases especiales de PDA se pueden minimizar o "recortar". Aquí también se pueden emplear algoritmos de optimización de aprendizaje automático de "terminación no garantizada", por ejemplo, algoritmos genéticos. Aquí hay dos documentos sobre "empujar visiblemente los autómatas" de una subclase. 2 documentos de ejemplo en esta línea:

vzn
fuente