I'm looking for examples of formal languages for Chomsky Type-0 to Type-3. While it is very simple to find examples for Type-1, Type-2, and Type-3, it is extremely hard for me to construct a simple example for Type-0, which is not Type-1.

Here are my exampes for Type-1 to Type-3:

Type-1: L1 = { anbncn | n ∈ ℕ }

Type-2: L2 = { anbn | n ∈ ℕ }

Type-3: L3 = { an | n ∈ ℕ }

An example for a Type-0 language which not that simple is the set of codes for turing machines which terminate for an empty input. While this is easy to express, it is not easy to imagine how elements of this set look like. Moreover, for understanding what this definition of a language actually means, one needs to have understood turing machines and the halting problem, which I think is a rather big requirement.

  • $\begingroup$ You're looking for a recursively enumerable language that is not recursive. One such language is the language of logical validities in first-order logic. $\endgroup$ Mar 14, 2015 at 16:54
  • $\begingroup$ Whoops, I meant you're looking for a recursively enumerable language (type 0) that is not context-sensitive (type 1). But the same example works; it's just stronger than is necessary. I don't know off the top of my head a recursive language that isn't type 1. $\endgroup$ Mar 14, 2015 at 17:11

1 Answer 1


The most elementary example that I’ve seen is from Theorem $11.11$ in Peter Linz, An Introduction to Formal Languages and Automata, and is basically a diagonalization argument. If we assume that the non-terminals are all from the set $\{V_n:n\in\Bbb N\}$, with $V_0$ as initial non-terminal, we can represent any context-sensitive grammar on the alphabet $\{a,b\}$ as a string

$$x_1\to y_1;x_2\to y_2;\ldots;x_m\to y_m$$

of symbols from the alphabet $\{a,b,;,\to\}\cup\{V_n:n\in\Bbb N\}$. These strings can then be encoded as elements of the regular set $R$ of binary strings corresponding to the regular expression $(011^*0)^*$ by the map

$$\begin{align*} a&\mapsto 010\\ b&\mapsto 01^20\\ ;&\mapsto 01^30\\ \to&\mapsto 01^40\\ V_n&\mapsto 01^{n+5}0\;. \end{align*}$$

Order $\{0,1\}^+$ by shortlex order and use it to enumerate $R=\{w_n:n\in\Bbb N\}$. Now let

$$L=\{w_n\in R:w_n\text{ defines a context-sensitive grammar }G_n\text{ and }w_n\notin L(G_n)\}\;.$$

It’s not hard to check that $L$ is recursive: checking that $w_n$ defines a context-sensitive grammar is mechanical, and if $G_n$ is such a grammar, then it’s non-contracting, so we can mechanically test whether $w_n\in L(G_n)$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .