„Prosty” język poza

Szukam języka L o następujących właściwościach:

1. L nie powinien być pozbawiony kontekstu.

2. Uzupełnienie L nie powinno być pozbawione kontekstu. (Wszystko, co widzisz w podręcznikach jako główny przykład języków bezkontekstowych, wydaje się nie spełniać tego drugiego wymogu).

3. L nie powinien być zbyt trudny. Na przykład wiem, że nierozstrzygalne języki spełniają dwa pierwsze wymagania, ale chcę, aby język był prostszy, który można rozpoznać po nieco „ulepszonym” modelu automatu, np. Probabilistycznym automacie wypychania.

Oto inny przykład:

, gdzie E P = { n b n c n | n ≥ 0 } i Ż E Q jest dopełnieniem E Q .$\mathtt{L} = \{ x\#y \mid x \in \mathtt{EQ},y \in \overline{\mathtt{EQ}} \}$
$\mathtt{EQ}=\{ a^nb^nc^n \mid n \geq 0 \}$$\overline{\mathtt{EQ}}$$\mathtt{EQ}$

Jest dobrze znanym faktem, że nie znajduje się w C F L .$\mathtt{EQ}$$\mathsf{CFL}$

$\mathtt{L}$$\small \mathcal{P_1}$$\small \mathcal{P}'$$w$$\small \mathcal{P}'$$\small \mathcal{P}_1$$w\#a$$\small \mathcal{P}'$$\mathtt{EQ}$$\mathtt{L} \notin \mathsf{CFL}$

$\mathtt{L}$$\small \mathcal{P}_2$$\small \mathcal{P}''$$w$$\small \mathcal{P}''$$\small \mathcal{P}_2$$\#w$$\small \mathcal{P}''$$\mathtt{EQ}$$\mathtt{L}$$\mathsf{coCFL}$

$\mathtt{EQ}$ może być rozpoznany przez (jednokierunkowy) probabilistyczny automat z jednym licznikiem (P1CA) z dowolnym pożądanym ograniczeniem błędu ( Freivalds, 1979 ). Tak więc nie jest trudno wykazać, że może być również rozpoznany przez P1CA z dowolnym pożądanym błędem.$\mathtt{L}$

Co powiesz na ? Łatwo zauważyć, że i jego uzupełnienie nie są regularne, a zatem (ponieważ mamy do czynienia z jednoargumentowym alfabetem) nie są kontekstowe.$L:=\{a^{n^2}\mid n\in\mathbb{N}\}$$L$

$QSAT$ lub nawet są przykładami, chyba że odpowiednio lub . jest przykładem, jak to jest -Complete i .$SAT$$P = PSPACE$$P = NP$$SAT$$NP$$CFL \subseteq P$

$QSAT$ (prawdziwe ilościowo formuły boolowskie) jest i jest CSL, rozpoznawalnym przez LBA.$PSPACE$

W przypadku bezwarunkowych przykładów możesz wziąć dowolny problem z , taki jak uogólniony Szachy lub Go.$EXP$