Entscheidbarkeit der Gleichheit der CFLs

11

Das folgende Problem ist entscheidbar:

Bei einer kontextfreien Grammatik ist L ( G ) = ?GL(G)=

Das folgende Problem ist unentscheidbar:

Bei einer kontextfreien Grammatik ist L ( G ) = A * ?GL(G)=A

Gibt es eine Charakterisierung kontextfreier Sprachen mit entscheidbarer Gleichheit L ( G ) = M ?ML(G)=M

sdcvvc
quelle
1
Crosspost von math.SE .
SDCVVC
1
Zum Beispiel ist es entscheidbar, wann endlich (einfach) ist, wann M = { a } (nach Parikhs Theorem) oder wann M = { a n b n } (nach Parikh und Überprüfung des Schnittpunkts mit dem Komplement von a b )MM={a}M={anbn}ab
SDCVVC
GL(G)
Ich denke das ist genau die Frage.
Domotorp
@Kaveh: Ich weiß nicht, ob dieses Set entscheidbar ist, obwohl es anscheinend nicht so ist. Die beste Antwort wären entweder einige "einfache" Bedingungen, die alle Fälle abdecken, oder Beispiele, die zeigen, dass das Phänomen zu komplex ist. Es ist ein bisschen vage, aber ich denke, es ist verantwortlich.
SDCVVC

Antworten:

7

Ich bin nicht sicher, ob es eine allgemeine Charakterisierung für die Äquivalenz gibt, aber die folgenden Arbeiten von Hopcroft, Hunt und Rosenkrantz resp. könnte ein guter Anfang sein:

  • John E. Hopcroft, Zu den Äquivalenz- und Eindämmungsproblemen für kontextfreie Sprachen, Theory of Computing Systems 3 (2): 119-124, doi: 10.1007 / BF01746517 ;
  • Harry B. Hunt, III und Daniel J. Rosenkrantz, Über Äquivalenz- und Eindämmungsprobleme für formale Sprachen, Journal of the ACM 24 (3): 387-396, 1977, doi: 10.1145 / 322017.322020 .

ML(G)=MMnw1,w2,,wnMw1w2wn

Sylvain
quelle
-2

Tut mir leid, einen alten Thread aufzurufen. Aber hier ist etwas, das relevant sein könnte.

Sei pCFL die Klasse der permutationsgeschlossenen CFLs. Das Gleichstellungsproblem für pCFL ist entscheidbar.

LΣ={σ1,,σn}WL={#a1(w),,#an(w)wL}WLL

LwL#a1(w),,#an(w)WLL1,L2L1=L2WL1=WL2

Dies wirft eine Frage auf, auf die ich die Antwort wissen möchte: Ist es entscheidbar, ob eine bestimmte kontextfreie Sprache permutationsgeschlossen ist?

Shane Steinert-Threlkeld
quelle
2
Dies ist keine Antwort auf die ursprüngliche Frage, sondern eine separate (obwohl verwandte) Frage. Sie sollten es als eigene Frage (mit einem Link zurück zu dieser Frage) entweder hier oder auf CS.SE stellen .
Artem Kaznatcheev
1
Ja, bitte löschen Sie diese Antwort und veröffentlichen Sie sie als neue Frage (mit einem Link zu dieser)
Suresh Venkat
1
@SureshVenkat es scheint, dass der Benutzer dies am Ende dieser Frage stellt . Vielleicht wird eine neue Frage nicht benötigt.
Artem Kaznatcheev
2
pCFL