Co stanowi uzupełnienie języków bezkontekstowych?

Muszę wiedzieć, pod którą klasą CFL jest zamknięty, tj. Jaki zestaw jest uzupełnieniem CFL. Wiem, że CFL nie jest zamknięty pod dopełnieniem i wiem, że P jest zamknięty pod dopełnieniem. Ponieważ CFL PI może powiedzieć, że dopełnienie CFL jest zawarte w P (prawda?). Pozostaje pytanie, czy dopełnienie CFL jest właściwym podzbiorem P, czy całym P. Byłbym wdzięczny za wszelkie pomysły, jak pokazać, że dopełnienie CFL jest całym P (jeśli tak jest w przypadku). $\subsetneq$

complexity-theory formal-languages context-free closure-properties sets użytkownik432
źródło

Zamierzałem zamieścić to jako odpowiedź, ale nie odpowiada to na całe twoje pytanie: dopełnienie dowolnego CFL to R (rekurencyjne), ponieważ języki rekurencyjne są zamknięte pod dopełniaczem, a wszystkie CFL to R.

Eric

CFL nie jest zamknięty w ramach komplementacji nie oznacza, że „L” w CFL oznacza, że jego dopełniacz nie jest w CFL. Oznacza to po prostu, że istnieje „L” w CFL, tak że jego dopełnienie nie występuje w CFL

SHREYANSHU THAKUR

@Eric Pytający już wie, że uzupełnienie dowolnego CFL jest rekurencyjne. Zrobili się znacznie silniejsze oświadczenie, że dopełnieniem każdej CFL jest w P .

David Richerby

Odpowiedzi:

Pytanie można zrozumieć na dwa sposoby, zgodnie z definicją „uzupełnienia CFL”.

przypadek A: Uzupełnieniem CFL jest klasa wszystkich języków, których nie ma w CFL. Formalnie W takim przypadku jest znacznie większy niż , ma nawet języki, które nie są w itp. Ale może nie o to ci chodziło.

\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$

przypadek B: Zdefiniuj klasę dopełniacza-CFL jako słowy, zestaw wszystkich języków , tak aby dopełnienie było wolne od kontekstu .

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

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

L

$L$

L

$L$

W takim przypadku to, co napisałeś, ma sens: (według algorytmu CYK ), a także (uruchom ten sam algorytm, odwrotną odpowiedź), a ponieważ , to powinno być natychmiastowe, że , prawda? $CFL \subsetneq P$ $co{CFL} \subseteq P$ $CFL \neq co{CFL}$ $co{CFL}\subsetneq P$

Ran G.
źródło

definicja CFK, o ile rozumiem: język L jest w coCFK wtedy i tylko wtedy, gdy uzupełnienie L jest w CFK. Przez dopełnienie LI rozumie się wszystkie możliwe ciągi oprócz ciągów w L. Problemem myślę, że dopełniacza nie można zdefiniować jako „uruchom ten sam algorytm i odwróć odpowiedź” Na przykład: L = (x ^ iy ^ iz ^ i) nie jest CFL, ale nie wiem, jaki algorytm mogę uruchomić, aby uzyskać (negatywną) odpowiedź.

user432,

więc odnosisz się do przypadku B. Zauważ, że dopełnienie CFL może nie być CFL, ale to nie znaczy, że algorytm CYK nie działa na nim tak samo. Mam na myśli, że uruchamiamy CYK na , który jest CFL i uzyskać odpowiedź dla każdego , czy nie jest w . przeciwieństwem jest odpowiedź na pytanie, czy jest w , nawet jeśli może nie być CFL.

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 jest tutaj twoim standardem notacji? Spodziewałbym się i klasa języków takich, że .

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

Właściwie pozwól mi zmienić notację zgodnie z twoją sugestią, będzie to miało większy sens.

Ran G.

Solidną klasą, która zawiera zarówno CFL, jak i coCFL jest LOGCFL , który zawiera wszystkie języki, które można sprowadzać do przestrzeni logicznej do języka bezkontekstowego. Ta klasa jest pośrednia między NL a AC1 i ma pewne naturalne kompletne problemy. Można to również zdefiniować w kategoriach ograniczonych obwodów AC1. LOGCFL jest zamknięty w dopełnieniu (jest to rozszerzenie argumentu używanego do pokazania, że NL = coNL).

Yuval Filmus
źródło

-1

Uzupełnieniem CFL może być CFL, ale niekoniecznie jest. Uzupełnienie CFL jest zarówno rekurencyjne (R), jak i rekurencyjnie policzalne (RE). Dlaczego? Wszystkie świetlówki kompaktowe są zarówno R, jak i RE. Języki R są zamknięte w uzupełnieniu (ale RE nie są). W tym kontekście uzupełnieniem CFL jest R, które z natury jest RE.

Loyola
źródło

Pytający już powiedział, że oni wiedzą, że dopełnieniem każdej WPRyb jest w P . To znacznie silniejsze stwierdzenie niż to, że jest rekurencyjne lub RE. To tak, jakby pytający wspomniał o osobie, która nie może chodzić, a ty odpowiedziałeś dowodem, że nie może biec z prędkością dźwięku.

David Richerby