<p>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.</p>

CC BY-SA 3.0
2011-11-24T09:41:50.363Z
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
CC BY-SA 3.0
2011-11-24T09:37:13.257Z
2011-11-24T09:37:13.257Z
Dominik D. Freydenberger
<p>$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$.</p>

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

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

CC BY-SA 3.0
2011-11-24T09:35:44.017Z
Yes, thanks, but any even simpler ones, preferably those in the class P, please?
Cem Say
CC BY-SA 3.0
2011-11-24T09:33:29.320Z
2011-11-24T09:33:29.320Z
Mike B.
<p>Here is another example:</p>

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

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

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

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

<p>$ \mathtt{EQ}$ can be recognized by a (one-way) probabilistic one-counter automaton (P1CA) with any desired error bound (<a href="http://www.springerlink.com/content/p679q6712h1047jp/">Freivalds, 1979</a>). So, it is not hard to show that $\mathtt{L}$ can also be recognized by a P1CA with any desired error bound. </p>

CC BY-SA 3.0
2011-11-25T22:40:02.077Z
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
CC BY-SA 3.0
2011-11-25T23:26:28.797Z
@CemSay: PPDAs cannot recognize any tally nonregular language with bounded error, too [Kaneps et al.](http://dl.acm.org/citation.cfm?id=646974.711387)
Abuzer Yakaryilmaz
CC BY-SA 3.0
2011-11-25T18:25:31.663Z
2011-12-05T09:29:39.593Z
2011-12-05T09:29:39.593Z
Abuzer Yakaryilmaz
<p>I am looking for a language L with the following properties:</p>

<ol>
<li><p>L should not be context-free.</p></li>
<li><p>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.)</p></li>
<li><p>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.</p></li>
</ol>

<fl.formal-languages><automata-theory>
A "simple" language outside $CFL \cup coCFL$?
Cem Say
# A "simple" language outside $CFL \cup coCFL$?

(Asked by: username_0 on 2011-11-24)

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.

**Tags:** fl.formal-languages, automata-theory

---

## 3 answers

### Answer by username_3 on 2011-11-25. Score: 16 | Accepted answer

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](http://www.springerlink.com/content/p679q6712h1047jp/)). So, it is not hard to show that $\mathtt{L}$ can also be recognized by a P1CA with any desired error bound.

> **Comments:**
> **username_0**: 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.)  
> **username_3**: @CemSay: PPDAs cannot recognize any tally nonregular language with bounded error, too [Kaneps et al.](http://dl.acm.org/citation.cfm?id=646974.711387)  

---

### Answer by username_1 on 2011-11-24. Score: 24

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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_2 on 2011-11-24. Score: 4

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

> **Comments:**
> **username_0**: Yes, thanks, but any even simpler ones, preferably those in the class P, please?  

---

