Eine „einfache“ Sprache außerhalb von

Ich suche eine Sprache L mit folgenden Eigenschaften:

1. L sollte nicht kontextfrei sein.

2. Ls Komplement sollte nicht kontextfrei sein. (Alles, was Sie in Lehrbüchern als Paradebeispiele für nicht kontextfreie Sprachen sehen, scheint diese zweite Anforderung nicht zu erfüllen.)

3. L sollte nicht zu schwer sein. Zum Beispiel weiß ich, dass unentscheidbare Sprachen die ersten beiden Anforderungen erfüllen, aber ich möchte eine einfachere Sprache, die von einem leicht "verbesserten" Automatenmodell erkannt werden kann, z. B. einem probabilistischen Pushdown-Automaten.

Hier ist ein weiteres Beispiel:

, wobei E Q = { a n b n c n | n ≥ 0 } und ¯ E Q das Komplement von ist 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}$

Es ist eine bekannte Tatsache, dass nicht in C F L ist .$\mathtt{EQ}$$\mathsf{CFL}$

Angenommen, wird von einem PDA P 1 erkannt . Wir konstruieren einen neuen PDA P ′ . Am Eingang W , P ' simuliert P 1 auf der Saite W # ein . Da P ' deutlich erkennt E Q , schließen wir , dass 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}$

Ebenso sei angenommen, dass das Komplement von von einem PDA P 2 erkannt wird . Wir bauen einen weiteren PDA P " . Bei Eingabe w , P " simuliert P 2 auf der Saite # w . P " erkennt auch E Q , so dass L auch nicht in c o C F L sein kann.$\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}$

kann von einem (einseitigen) probabilistischen Ein-Zähler-Automaten (P1CA) mit beliebiger Fehlergrenze erkannt werden (Freivalds, 1979). Es ist also nicht schwer zu zeigen, dass L auch von einem P1CA mit einer beliebigen Fehlergrenze erkannt werden kann.$\mathtt{EQ}$$\mathtt{L}$

Wie wäre es mit ? Es ist leicht zu erkennen, dass L und sein Komplement nicht regelmäßig sind und daher (da es sich um ein unäres Alphabet handelt) nicht kontextfrei sind.$L:=\{a^{n^2}\mid n\in\mathbb{N}\}$$L$

oder S A T sind Beispiele, es sei denn , P = P S P A C E oder P = N P verbunden. S A T ist ein Beispiel, da es N P -komplett und C F L ⊆ P ist .$QSAT$$SAT$$P = PSPACE$$P = NP$$SAT$$NP$$CFL \subseteq P$

(wahre quantifizierte Boolesche Formeln) ist P S P A C E -vollständig und ist eine CSL, die durch eine LBA erkennbar ist.$QSAT$$PSPACE$

Für bedingungslose Beispiele können Sie ein beliebiges -vollständiges Problem verwenden, z. B. verallgemeinertes Schach oder Go.$EXP$