1
$\begingroup$

I've been reading the decidablity and undecidability chapters in Sipser's "Intro to Theory of Computation" however I could not find an explanation on the existence of a language that is both non-context free and decidable.

The only reference to this was a simple language hierarchy diagram showing where the decidable/recognisable bounds were in relation to language types.

I'm unsure as to how I should approach this but I've thought about proving this by diagonlisation:

  • Let $M$ be the set of all decideable Turing Machines, and $L$ the set of all languages that are context-free. (Assume finite alphabet)
  • By drawing up and filling the table where each language corresponds to a Turing Machine, I was hoping that I could find a contradiction in some $m \in M$ where there is no corresponding language $l \in L$.

I know that this will not work as both $M$ and $L$ are countable.

Any ideas on how I should approach this?

$\endgroup$
6
  • 1
    $\begingroup$ Most decidable languages are not context-free. The classic example is a^nb^nc^n. See Wikipedia for more info: en.wikipedia.org/wiki/… $\endgroup$
    – Mark VY
    Apr 21 '17 at 3:41
  • $\begingroup$ If the book does not equip you to answer this for yourself in 30s, throw it away. My guess is you have to read on (or more closely). $\endgroup$
    – Raphael
    Apr 21 '17 at 5:15
  • $\begingroup$ Okay, I used very poor choice of words to describe what I was really after, rather than "explanation" I was meant to say "explicit proof". Sipser used the diagonalisation argument to show that there exists an undecideable language for $A_{TM}$ which I understood, and I wanted to try do the same, to show the existence of a decideable and non-context-free language as I remember seeing a question that asked for this using a diagonalisation proof. I should have asked this question on the diagonlisation method itself rather than under the concept of decideable context-free languages. $\endgroup$
    – J Z
    Apr 21 '17 at 8:54
  • 1
    $\begingroup$ Possible duplicate of How to prove that a language is not context-free? $\endgroup$ Apr 21 '17 at 11:05
2
$\begingroup$

You could simply consider the language $L = \{a^k | k \text{ is a prime number }\}$. This is not a context free language, but surely this is decidable by a Turing Machine that checks if the length N of the input is not divisible by any number between 2 and N-1 .

$\endgroup$
1
$\begingroup$

I had not the enough reputation in this community to leave a comment on @Umamg's answer; so, I try to complete Umang's answer in mine.

One way to show that the language $L=\{a^p: \text{p is a prime number}\}$ is not context-free is to use pumping lemma for CFLs in the following way:

If $L$ was a CFL, then given an arbitrary long string in this language, say $a^p$ with $p$ being greater than the pumping length of $L$, this string would be decomposed into five parts $uvxyz$ with $|vy|\geq 1$ and so that for any $i\geq 0$ the string $uv^ixy^iz$ would belong to $L$.

Let $l:=|vy|$, then the above discussion shows that all the following strings are part of the language $L$: $$a^p, a^{p+l}, a^{p+2l}, \ldots, a^{p+nl}, \ldots$$

That is, the set of prime numbers contains an infinite arithmetic progression which is impossible since the number $p+pl$ is divisible by p.

$\endgroup$
0
$\begingroup$

There are two quick answers within easy reach of undergrad courses:

  1. CFL ⊊ CSL ⊊ R
  2. CFL ⊊ P ⊊ R

Basically, "all" of complexity theory happens "between" CFL and R (with some notable exceptions). Just have a look at the complexity zoo and note how far down CFL is, and how far up R.

$\endgroup$
0
$\begingroup$

A direct diagonalization argument is very much usable here (even though a somewhat unorthodox choice, as we have "more natural" separating examples available to us).

We can construct in a straight-forward way a notation system for context-free grammars, which then lifts to a notation system $(L_w)_{w \in \Sigma^*}$ for the context-free languages. We can then define the diagonal language $L_\Delta = \{w \in \Sigma^* \mid w \notin L_w\}$. The usual proofs that each context-free language is decidable are all uniform in the grammar, and thus give us that $L_\Delta$ is decidable. By construction, $L_\Delta$ is not context-free.

Everything in the preceeding paragraph remains true if we replace "context-free" by "context-sensitive".

$\endgroup$

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.