¿Un lenguaje "simple" fuera de

Estoy buscando un lenguaje L con las siguientes propiedades:

1. L no debe estar libre de contexto.

2. El complemento de L no debe estar libre de contexto. (Todo lo que ves en los libros de texto como ejemplos principales de lenguajes sin contexto parece fallar en este segundo requisito).

3. No debería ser demasiado difícil. Por ejemplo, sé que los lenguajes indecidibles se ajustan a los dos primeros requisitos, pero lo que quiero es un lenguaje más simple que pueda ser reconocido por un modelo de autómata ligeramente "mejorado", por ejemplo, un autómata de empuje probabilístico.

Aquí hay otro ejemplo:

, donde E Q = { a n b n c n | n ≥ 0 } y ¯ E Q es el complemento de 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 un hecho bien conocido que no está en C F L .$\mathtt{EQ}$$\mathsf{CFL}$

Suponga que es reconocido por un PDA P 1 . Construimos un nuevo PDA P ′ . En la entrada w , P ' simula P 1 en la cadena w # a . Desde P ' reconoce claramente E Q , llegamos a la conclusión de que 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}$ puede ser reconocido por un autómata de un contador probabilístico (unidireccional) (P1CA) con cualquier límite de error deseado ( Freivalds, 1979 ). Por lo tanto, no es difícil demostrar que también puede ser reconocido por un P1CA con cualquier error deseado vinculado.$\mathtt{L}$

¿Qué tal ? Es fácil ver que y su complemento no son regulares y, por lo tanto (como estamos tratando con un alfabeto unario), no están libres de contexto.$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$ o incluso son ejemplos, a menos que o respectivamente. es un ejemplo, ya que es -Complete y .$SAT$$P = PSPACE$$P = NP$$SAT$$NP$$CFL \subseteq P$

P S P A C $QSAT$ (verdaderas fórmulas booleanas cuantificadas) es -complete, y es un CSL, reconocible por un LBA.$PSPACE$

Para ejemplos incondicionales, puede tomar un problema arbitrario de -completo, como Ajedrez generalizado o Go.$EXP$