«Простой» язык вне

Я ищу язык L со следующими свойствами:

1. L не должен быть контекстно-свободным.

2. Дополнение L не должно быть контекстно-свободным. (Все, что вы видите в учебниках как главные примеры неконтекстно-свободных языков, похоже, не соответствует этому второму требованию.)

3. L не должен быть слишком сложным. Например, я знаю, что неразрешимые языки соответствуют первым двум требованиям, но мне нужен более простой язык, который может быть распознан слегка «улучшенной» моделью автомата, например, вероятностный автомат с понижением.

Вот еще один пример:

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

Это хорошо известный факт , что $\mathtt{EQ}$ не в $\mathsf{CFL}$ .

Предположим, что распознается КПК P 1 . Мы строим новый КПК P ′ . На входе ш , Р ' имитирует P 1 на строку ш # а . Так как P ' четко признает E Q , мы приходим к выводу , что L ∉ C F L . $\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$ w P ″ P 2 #w P ″ EQLcoCF$\small \mathcal{P}''$$w$$\small \mathcal{P}''$$\small \mathcal{P}_2$$\#w$$\small \mathcal{P}''$$\mathtt{EQ}$$\mathtt{L}$$\mathsf{coCFL}$

$\mathtt{EQ}$ может быть распознан (односторонним) вероятностным автоматом с одним счетчиком (P1CA) с любой требуемой границей ошибки ( Freivalds, 1979 ). Таким образом, нетрудно показать, что также может быть распознан P1CA с любой желаемой границей ошибки.$\mathtt{L}$

Как насчет ? Легко видеть, что и его дополнение не являются регулярными и, следовательно, (как мы имеем дело с унарным алфавитом) не являются контекстно-свободными.$L:=\{a^{n^2}\mid n\in\mathbb{N}\}$$L$

S A T P = P S P A C E P = N P S A T N P C F L ⊆ $QSAT$ или даже являются примерами, если или соответственно. является примером, как это -полное и .$SAT$$P = PSPACE$$P = NP$$SAT$$NP$$CFL \subseteq P$

P S P A C $QSAT$ (истинные количественные логические формулы) является полным и является CSL, распознаваемым LBA.$PSPACE$

Для безусловных примеров вы можете взять произвольную полную задачу, такую ​​как обобщенные шахматы или го.$EXP$