Ist es möglich, Pushdown-Automaten zu minimieren?

8

Ist es möglich, Pushdown-Automaten zu minimieren? Wenn nein, warum? Liegt es daran, dass die Äquivalenzklassen zur Minimierung einen endlichen Index haben müssen und wir dies für CFG nicht garantieren können?

computability automata pushdown-automata Tom J.
quelle

Antworten:

8

Leider ist das Problem nicht berechenbar. Es ist nicht zu entscheiden, ob zwei beliebige PDAs gleichwertig sind. Das Minimieren eines PDA ist noch schwieriger.

DW
quelle
6

Ich antwortete im Grunde die gleiche Frage (allgemeinen setzen) hier .

Das Argument in Kürze: Wenn Sie dies tun könnten, könnten Sie die Universalität und einige andere unentscheidbare Eigenschaften von PDA / CFG bestimmen. Daher kann es durch Reduktion keinen solchen Minimierer geben.

Raphael
quelle
4

Entschuldigung, in Bezug auf was minimieren?

Jeder PDA hat einen äquivalenten PDA mit einem einzigen Status.

Hendrik Jan.
quelle
Huh, stimmt. :) Ich denke "Größe einer vernünftigen Codierung", zB die Übergangstabelle. Die anderen Antworten würden damit funktionieren, nicht wahr?
Raphael
2

Ich weiß nicht, wie Sie mit Nicht-Pushdown-Automaten minimieren sollen, aber ...

Sie können ein CFG in einen PDA konvertieren, oder? Und diese Konvertierung hat laut Hopcroft nur einen Status, der sehr minimiert ist, finden Sie nicht? Alles, was Sie tun müssen, ist, Ihren PDA in CFG umzuwandeln und dann Ihre CFG wieder in PDA umzuwandeln. Sie haben einen PDA mit 1 Status.

H_DANILO
quelle
Beachten Sie, dass dies ein minimaler Zustand ist, aber kein minimaler Übergang. Wie DW sagt, ist es nicht berechenbar, den Übergang und den Zustand minimal zu machen.
jmite
0

"minimieren" bedeutet normalerweise "globales Minimum", kann sich aber manchmal auf ein "lokales Minimum" beziehen. In diesem Fall gibt es Heuristiken, dh Strategien, die zu einer gewissen Reduzierung führen können, aber das globale Minimum nicht konsistent finden. und auch einige spezielle Klassen von PDAs können minimiert oder "getrimmt" werden. Algorithmen zur Optimierung des maschinellen Lernens mit "nicht garantierter Beendigung", z. B. genetische Algorithmen, können auch hier verwendet werden. Hier sind zwei Artikel über "sichtbar heruntergedrückte Automaten" einer Unterklasse. 2 Beispielpapiere in dieser Richtung:

vzn
quelle