Ist die Gleichwertigkeit eindeutiger kontextfreier Sprachen bestimmbar?

19

Es ist allgemein bekannt, dass das Äquivalenzproblem für allgemeine kontextfreie Sprachen nicht zu entscheiden ist. Alle Beweise für diese Tatsache, die mir bekannt sind, scheinen jedoch nicht eindeutige kontextfreie Grammatiken zu enthalten. Aus diesem Grund möchte ich fragen, ob bekannt ist, ob das Problem weiterhin unentscheidbar ist, während man sich auf eindeutige kontextfreie Sprachen beschränkt. Das heißt, wenn zwei kontextfreie Grammatiken von vornherein als eindeutig eingestuft werden, ist es dann entscheidend, ob sie gleichwertig sind oder nicht?

Ich finde dieses Problem ein wenig faszinierend, da es bekannt ist, dass Äquivalenz für deterministische kontextfreie Sprachen entscheidend ist, obwohl dieses Ergebnis alles andere als trivial ist ... Andererseits könnte es einen einfachen Grund für meine Unentschlossenheit geben übersehen.

fl.formal-languages grammars context-free decidability undecidability Jára Cimrman
quelle
3
Einbeziehung ist unentscheidbar: pdfs.semanticscholar.org/afdb/…
Peter Leupold
4
@PeterLeupold Ja, aber die Einbeziehung ist auch für deterministische kontextfreie Sprachen nicht entscheidend. Dies ist also recht einfach (der Artikel, auf den Sie verlinken, gibt nur einen Beweis, ohne diesen Fakt zu verwenden). Die Äquivalenz scheint jedoch viel interessanter zu sein, da dies für deterministische kontextfreie Sprachen und für allgemeine kontextfreie Sprachen unentscheidbar ist ...
Jára Cimrman
3
Trotzdem vermute ich, dass dieses Problem offen sein könnte: Ein Beweis für die Entscheidbarkeit ist kaum bekannt, da der für deterministische CFLs ziemlich kompliziert ist; Andererseits würde Unentscheidbarkeit Unentscheidbarkeit der Äquivalenz von algebraischen Reihen in nichtkommutativen Variablen bedeuten , was, wenn ich alles richtig verstehe, ein offenes Problem sein sollte. N
Jára Cimrman

Antworten:

9

Dies ist derzeit ein offenes Problem. Wie richtig ausgeführt, wird erwartet, dass der Beweis schwierig ist, wenn er entscheidbar ist, da er das berühmte DPDA-Äquivalenzproblem verallgemeinert. Andererseits bedienen sich die klassischen Argumente für die Unentscheidbarkeit des CFL-Universalitätsproblems von Natur aus mehrdeutiger Sprachen, und daher braucht man neue Ideen, um Unentscheidbarkeit aufzuzeigen.

Lassen Sie mich darauf hinweisen, dass das Universalitätsproblem für UCFLs (in PSPACE) mithilfe von Generierungsfunktionen entscheidbar ist [1].

VERWEISE

[1] N. Chomsky und MP Schützenberger, The Algebraic Theory of Context-Free Languages, Computerprogrammierung und formale Systeme, 1963.

Lorenzo
quelle
2
Ich denke, Sie meinen von Natur aus mehrdeutige Sprachen.
Emil Jeřábek unterstützt Monica am
in der Tat, danke @ EmilJeřábek dafür, dass er dies entdeckt hat
Lorenzo