12
$\begingroup$

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.

Improve this question
$\endgroup$
15
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$ – Cem Say Nov 25 '11 at 22:40
  • $\begingroup$ @CemSay: PPDAs cannot recognize any tally nonregular language with bounded error, too Kaneps et al. $\endgroup$ – Abuzer Yakaryilmaz Nov 25 '11 at 23:26
22
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Cem Say Nov 24 '11 at 9:41
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, thanks, but any even simpler ones, preferably those in the class P, please? $\endgroup$ – Cem Say Nov 24 '11 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.