# A “simple” language outside $CFL \cup coCFL$?

I am looking for a language L with the following properties:

1. L should not be context-free.

2. L's complement should not be context-free. (Everything you see in textbooks as prime examples of non-context-free languages seem to fail this second requirement.)

3. L shouldn't be too hard, For example, I know that undecidable languages fit the first two requirements, but what I want is a simpler language which can be recognized by a slightly "improved" automaton model, e.g. a probabilistic pushdown automaton.

Here is another example:

$\mathtt{L} = \{ x\#y \mid x \in \mathtt{EQ},y \in \overline{\mathtt{EQ}} \}$,
where $\mathtt{EQ}=\{ a^nb^nc^n \mid n \geq 0 \}$ and $\overline{\mathtt{EQ}}$ is the complement of $\mathtt{EQ}$.

It is a well known fact that $\mathtt{EQ}$ is not in $\mathsf{CFL}$.

Assume that $\mathtt{L}$ is recognized by a PDA $\small \mathcal{P_1}$. We construct a new PDA $\small \mathcal{P}'$. On input $w$, $\small \mathcal{P}'$ simulates $\small \mathcal{P}_1$ on the string $w\#a$. Since $\small \mathcal{P}'$ clearly recognizes $\mathtt{EQ}$, we conclude that $\mathtt{L} \notin \mathsf{CFL}$.

Similarly, assume that the complement of $\mathtt{L}$ is recognized by a PDA $\small \mathcal{P}_2$. We build another PDA $\small \mathcal{P}''$. On input $w$, $\small \mathcal{P}''$ simulates $\small \mathcal{P}_2$ on the string $\#w$. $\small \mathcal{P}''$ also recognizes $\mathtt{EQ}$, so $\mathtt{L}$ can not be in $\mathsf{coCFL}$ either.

$\mathtt{EQ}$ can be recognized by a (one-way) probabilistic one-counter automaton (P1CA) with any desired error bound (Freivalds, 1979). So, it is not hard to show that $\mathtt{L}$ can also be recognized by a P1CA with any desired error bound.

• Even better than Dominik's answer, since it also describes a PPDA recognizing the language! (Dominik's is a tally language, and I have no idea how to build a PPDA that's superior to a PDA regarding a tally language.) – Cem Say Nov 25 '11 at 22:40
• @CemSay: PPDAs cannot recognize any tally nonregular language with bounded error, too Kaneps et al. – Abuzer Yakaryilmaz Nov 25 '11 at 23:26

How about $L:=\{a^{n^2}\mid n\in\mathbb{N}\}$? It is easy to see that $L$ and its complement are not regular, and hence (as we are dealing with a unary alphabet) not context-free.

• That's it, thanks. This is what my question asked for, so I'm accepting it, but I would appreciate any other examples very much. – Cem Say Nov 24 '11 at 9:41

$QSAT$ or even $SAT$ are examples, unless $P = PSPACE$ or $P = NP$ respectively. $SAT$ is an example, as it is $NP$-complete and $CFL \subseteq P$.

$QSAT$ (true quantified boolean formulas) is $PSPACE$-complete, and is a CSL, recognizable by a LBA.

For unconditional examples you can take an arbitrary $EXP$-complete problem, such as generalized Chess or Go.

• Yes, thanks, but any even simpler ones, preferably those in the class P, please? – Cem Say Nov 24 '11 at 9:35