⟸ pàgina anterior ⟸
Exercici 6 (Tasca 5).
(RE (semi-decidable/ recursively enumerable languages))

Alguns llenguatges a \mathbf{RE}

Demostreu que els llenguatges següents pertanyen a \mathbf{RE}:

  1. \{\langle x,y\rangle \mid M_x(y)\downarrow\}. En altres paraules, aquest és el llenguatge de tots els parells on el primer component x és el nombre de Gödel d’una màquina de Turing M_x i la màquina s’atura quan se li dona com a entrada el segon component y.
  2. \{x \mid \exists y\ M_x(y)\downarrow\}. En altres paraules, aquest és el llenguatge de tots els x tals que x és el nombre de Gödel d’una màquina de Turing M_x que s’atura en alguna entrada.
  3. \{\langle u,v,R\rangle \mid u\to^* v\}. En altres paraules, aquest és el llenguatge de totes les triples on el primer i el segon components u,v codifiquen mots, el tercer component codifica un conjunt de regles de producció R i el mot v és derivable a partir de u aplicant les regles de R.
  4. \{G\in \mathtt{CFG} \mid G \text{ és ambigua}\}. En altres paraules, aquest és el llenguatge de totes les gramàtiques incontextuals ambigües.
  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\}. En altres paraules, aquest és el llenguatge de tots els parells de gramàtiques incontextuals amb intersecció no buida (és a dir, que generen algun mot en comú).