Examples for different types of formal languages

Question

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: L₁ = { aⁿbⁿcⁿ | n ∈ ℕ }

Type-2: L₂ = { aⁿbⁿ | n ∈ ℕ }

Type-3: L₃ = { aⁿ | 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.

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