Was ist die Ergänzung von kontextfreien Sprachen?

Ich muss wissen, welche Klasse von CFL geschlossen ist, dh welche Menge ist eine Ergänzung von CFL. Ich weiß, dass CFL nicht unter Komplement geschlossen ist, und ich weiß, dass P unter Komplement geschlossen ist. Da CFL PI sagen kann, dass das Komplement von CFL in P enthalten ist (richtig?). Es bleibt die Frage, ob das Komplement von CFL die richtige Teilmenge von P oder das gesamte P ist. Ich würde mich über Ideen freuen, wie gezeigt werden kann, dass das Komplement von CFL das gesamte P ist (wenn dies natürlich der Fall ist). $\subsetneq$

complexity-theory formal-languages context-free closure-properties sets user432
quelle

Ich wollte dies als Antwort posten, aber es beantwortet nicht Ihre ganze Frage: Das Komplement einer CFL ist R (rekursiv), da rekursive Sprachen unter Komplement geschlossen sind und alle CFLs R sind.

Eric

CFL, das nicht unter Komplementation geschlossen wird, bedeutet nicht, dass ein 'L' in CFL bedeutet, dass sein Komplement nicht in CFL ist. Es bedeutet nur, dass es in CFL ein 'L' gibt, so dass sein Komplement nicht in CFL ist

SHREYANSHU THAKUR

@Eric Der Fragesteller weiß bereits, dass das Komplement einer CFL rekursiv ist. Sie haben die viel stärkere Aussage gemacht, dass das Komplement einer CFL in P ist .

David Richerby

Antworten:

Man kann Ihre Frage auf zwei Arten verstehen, gemäß der Definition von "das Komplement von CFL".

Fall A: Komplement von CFL ist die Klasse aller Sprachen, die nicht in CFL enthalten sind. Formal ist In diesem Fall ist viel größer als , es gibt sogar Sprachen, die nicht in usw. sind. Aber vielleicht haben Sie das nicht gemeint.

\bar{C. F. L.} = {L. ∣ L. \notin C. F. L.}} .

$\overline{CFL} = \{ L \mid L\notin CFL\}.$

\bar{C F L}

$\overline{CFL}$

P

$P$

R

$R$

Fall B: Definieren Sie die Komplement-CFL-Klasse als in Worten die Menge aller Sprachen , so dass das Komplement von kontextfrei ist .

c Ö C. F. L. = {\bar{L.} ∣ L. \in C. F. L.}},

$co{CFL} = \{ \bar{L} \mid L \in CFL\},$

L

$L$

L

$L$

In diesem Fall ist das, was Sie geschrieben haben, sinnvoll: (nach dem CYK-Algorithmus ) und auch (denselben Algorithmus ausführen, die entgegengesetzte Antwort ausgeben) und seit , dann sollte es sofort sein, dass , richtig? $CFL \subsetneq P$ $co{CFL} \subseteq P$ $CFL \neq co{CFL}$ $co{CFL}\subsetneq P$

Ran G.
quelle

Definition von CFK, soweit ich es verstehe: Sprache L ist genau dann in coCFK, wenn das Komplement von L in CFK ist. Mit Komplement von LI sind alle möglichen Zeichenfolgen außer Zeichenfolgen in L gemeint. Das Problem ist meines Erachtens, dass Komplement nicht definiert werden kann als "den gleichen Algorithmus ausführen und die Antwort umkehren". Beispiel: L = (x ^ iy ^ iz ^ i) ist es nicht CFL, aber ich weiß nicht, welchen Algorithmus ich ausführen kann, um die (negative) Antwort zu erhalten.

user432

Sie beziehen sich also auf Fall B. Beachten Sie, dass das Komplement einer CFL

möglicherweise nicht CFL ist, aber dies bedeutet nicht, dass der CYK-Algorithmus nicht auf dieselbe Weise funktioniert. Ich meine, wir führen die CYK auf

, das ist CFL, und erhalten eine Antwort für jedes

unabhängig davon, ob es in

ist oder nicht . Das Gegenteil davon ist die Antwort auf die Frage, ob

ist oder nicht, obwohl

möglicherweise keine CFL ist.

L

$L$

\bar{L}

$\overline L$

x

$x$

\bar{L}

$\overline L$

x

$x$

L

$L$

L

$L$

Ran G.

@ user432

coCFL \neq \bar{CFL}

$\text{coCFL} \neq \overline{\text{CFL}}$

Raphael

@RanG ist hier Ihr Notationsstandard? Ich würde erwarten ,

und

die Klasse der Sprachen

, so dass

c o C F L = {L : \bar{L} \in C F L}

$coCFL = \{ L : \bar{L} \in CFL\}$

\bar{C F L} =

$\overline{CFL} =$

L

$L$

L \notin C F L

$L \not \in CFL$

Usul

Lassen Sie mich die Notation gemäß Ihrem Vorschlag ändern, es wird sinnvoller sein.

Ran G.

Eine robuste Klasse, die sowohl CFL als auch coCFL enthält, ist LOGCFL , die alle Sprachen enthält, deren Logspace auf eine kontextfreie Sprache reduziert werden kann. Diese Klasse liegt zwischen NL und AC1 und weist einige natürliche vollständige Probleme auf. Es kann auch in Form von eingeschränkten AC1-Schaltkreisen definiert werden. LOGCFL wird unter Komplement geschlossen (dies ist eine Erweiterung des Arguments, mit dem gezeigt wird, dass NL = coNL ist).

Yuval Filmus
quelle

-1

Komplement von CFL könnte möglicherweise CFL sein, ist es aber nicht unbedingt. Das Komplement der CFL ist sowohl rekursiv (R) als auch rekursiv aufzählbar (RE). Warum? Alle CFLs sind sowohl R als auch RE. R-Sprachen werden unter Komplement geschlossen (RE jedoch nicht). In diesem Zusammenhang ist das Komplement von CFL R, das von Natur aus RE ist.

Loyola
quelle

Der Fragesteller hat bereits gesagt, dass er weiß, dass die Ergänzung einer GFP in P ist . Das ist eine viel stärkere Aussage als die rekursive oder RE. Es ist, als hätte der Fragesteller eine Person erwähnt, die nicht laufen kann, und Sie haben mit einem Beweis geantwortet, dass sie nicht mit Schallgeschwindigkeit rennen kann.

David Richerby