⟸ pàgina anterior ⟸

Exercici 4 (Tasca 5).

(R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, complement, concatenation, Kleene star, shift)

Altres propietats de tancament de \mathbf{R}, \mathbf{RE} i \mathbf{coRE}

L’objectiu d’aquest exercici és veure com es comporten les classes \mathbf{R}, \mathbf{RE} i \mathbf{coRE} respecte de la complementació, la concatenació, l’estrella de Kleene i el shift.

Nota

Recordeu també que una classe \cal C de llenguatges és tancada per una operació binària \circ (per exemple, la unió o la intersecció) si per a tot A,B\in {\cal C}, es compleix que A \circ B \in {\cal C}. Similarment, \cal C és tancada per una operació unària \circ (per exemple, el complementari o el revessat) si per a tot A \in {\cal C}, es compleix que \circ A \in {\cal C}.

1. Complementari.

   1. Demostreu que \mathbf{R} és tancada per complementació.
   2. Demostreu que si A\in \mathbf{RE}, llavors \overline A\in \mathbf{coRE}.
   3. Demostreu que si A\in \mathbf{coRE}, llavors \overline A\in \mathbf{RE}.

2. Concatenació.

   1. Demostreu que \mathbf{R} és tancada per concatenació.
   2. Demostreu que \mathbf{RE} és tancada per concatenació.
   3. És \mathbf{coRE} tancada per concatenació?

3. Estrella de Kleene.

   1. Demostreu que \mathbf{R} és tancada per l’estrella de Kleene.
   2. Demostreu que \mathbf{RE} és tancada per l’estrella de Kleene.
   3. És \mathbf{coRE} tancada per l’estrella de Kleene?

4. Desplaçament (vegeu l’Exercici 1.9).

   1. Demostreu que \mathbf{R} és tancada per desplaçament.
   2. Demostreu que \mathbf{RE} és tancada per desplaçament.
   3. És \mathbf{coRE} tancada per desplaçament?