Berechnung der Schnittmenge zweier NPDA, wo dies möglich ist

Apropois zu Raffaels Vorschlag zum Schnittpunkt zweier NPDAs :

Sei und NPDA für die kontextfreien Sprachen bzw. . Unter der Annahme, dass wir wissen, dass kontextfrei ist, können wir NPDA für (effektiv) konstruieren ? $A_1$ $A_2$ $L_1$ $L_2$ $L = L_1 \cap L_2$ $A$ $L$

Jede Art von Algorithmus wäre akzeptabel, aber je praktischer, desto besser.

computability automata pushdown-automata soandos
quelle

Ein Beispiel für ein solches L, bei dem weder L1 noch L2 regulär sind und die Kreuzung nicht leer ist, könnte hilfreich sein. Gibt es ein solches L? Etwas ähnliche Probleme für NPDAs (Prüfung der Überschneidungsfreiheit, Prüfung der Gleichheit) sind nicht zu entscheiden. Schlagen Sie vor, zu tcs.se zu migrieren / zu befördern, wenn keine Antwort zustande kommt

vzn

@vzn Ich glaube, ich habe ein Beispiel mit ~ 50 Zuständen. Ich werde versuchen, jemanden zu finden, der minimaler ist

soandos

Die Zeichenfolgen "mindestens 1/3 1" und "weniger als 2/3 1" über dem Alphabet sind beide DCFLs, und ihre Schnittmenge ist eine CFL (und keine DCFL)

{0, 1}

$\{0,1\}$

sjmc

@sjmc kannst du einen Beweis skizzieren? Für mich nicht selbstverständlich. Ich stimme zu, wenn du es als Antwort postest, obwohl es keine vollständige Antwort ist. Es ist ein Fortschritt

vzn

update dies scheint bei tcs.se als unentscheidbar beantwortet zu werden, da die willkürliche TM-Berechnung als Schnittmenge zweier CFLs ausgedrückt werden kann.

VZN

Antworten:

Ich denke, dass dies für die Unterklasse von CFLs möglich ist, die mit einem binären Alphabet permutationsinvariant sind.

Diese entsprechen den Quantifizierersprachen vom Typ , die die Kardinalitäten zweier Mengen vergleichen. [1] charakterisiert solche von DPDA akzeptierten Sprachen durch die entsprechenden semilinearen Mengen und gibt am Ende an, dass von NPDA akzeptierte Quantifizierungssprachen endliche boolesche Kombinationen solcher von DPDA akzeptierten Sprachen sind. $\langle 1,1\rangle$

Ein Satz von van Benthem ([2]) besagt, dass Pushdown-Automaten Quantifizierer vom Typ akzeptieren, die in der Presburger-Arithmetik definierbar sind (dh durch semilineare Mengen definiert sind). Wenn Sie also zwei Sprachen erhalten, bei denen es sich um nicht deterministische CFLs handelt (unter Verwendung des ersten Papiers, bei dem Sie wissen, dass Sie solche Beispiele haben), sollte deren Schnittmenge ebenfalls eine CFL nach diesem Theorem sein. $\langle 1,1\rangle$

Die semilineare Menge, die ihre Schnittmenge ist, ist möglicherweise etwas schwierig zu berechnen. Wenn Sie diese haben, [3] (S. 11-12) geben Sie einen Algorithmus zum Erstellen eines NPDA an, der die Sprache auf der Grundlage der Generatoren von akzeptiert entsprechende semilineare Menge.

[1] Makoto Kanazawa. Monadische Quantierer, die von deterministischen Push-Down-Automaten erkannt werden . In Proceedings of the 19th Amsterdam Colloquium, Seiten 139-146, 2013.

[2] Johann van Benthem. Essays in Logical Semantics . Studies in Linguistics and Philosophy Volume 29, 1986, S. 151-176.

[3] Marcin Mostowski. Berechnungssemantik für monadische Quantoren . Journal of Applied Non-Classical Logics, 8 (1-2): 107-121, 1998.

sjmc
quelle