⟸ Go Back ⟸
Exercise 6 (Homework 5).
(RE (semi-decidable/ recursively enumerable languages))

Some languages in \mathbf{RE}

Show that the following languages belong to \mathbf{RE}:

  1. \{\langle x,y\rangle \mid M_x(y)\downarrow\}. In other words, this is the language of all pairs where the first entry x is the Gödel-number of a Turing machine M_x, and the machine terminates when given as input the second entry y.
  2. \{x \mid \exists y\ M_x(y)\downarrow\}. In other words, this is the language of all x, where x is the Gödel-number of a Turing machine M_x which terminates on some input.
  3. \{\langle u,v,R\rangle \mid u\to^* v\}. In other words, this is the language of all triplets where the first and second entries u,v encode words, the third entry a set of production rules R, and the word v is reachable from u using the production rules in R.
  4. \{G\in \mathtt{CFG} \mid G \text{ ambiguous}\}. In other words, this is the language of all ambiguous context-free grammars.
  5. \{\langle G_1,G_2\rangle \mid G_1,G_2\in \mathtt{CFG} \land \mathcal L(G_1)\cap \mathcal L(G_2)\neq \emptyset\}. In other words, this is the language of all pairs of context-free grammars with nonempty intersection (i.e., that generate some common word).