⟸ pàgina anterior ⟸

Exercici 3 (Tasca 5).

(R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, union, intersection, reverse)

\mathbf{R}, \mathbf{RE} i \mathbf{coRE} són tancades per unió, intersecció i revessat

L’objectiu d’aquest exercici és demostrar algunes propietats de tancament de \mathbf{R}, \mathbf{RE} i \mathbf{coRE}.

Nota

Recordeu 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. Unió. Demostreu les propietats següents:

   1. \mathbf{R} és tancada per unió.
   2. \mathbf{RE} és tancada per unió.
   3. \mathbf{coRE} és tancada per unió.

2. Intersecció. Demostreu les propietats següents:

   1. \mathbf{R} és tancada per intersecció.
   2. \mathbf{RE} és tancada per intersecció.
   3. \mathbf{coRE} és tancada per intersecció.
      

3. Diferència de conjunts. Demostreu la propietat següent:

   1. \mathbf{R} és tancada per la diferència de conjunts.

4. Revessat. Demostreu les propietats següents:

   1. \mathbf{R} és tancada pel revessat.
   2. \mathbf{RE} és tancada pel revessat.
   3. \mathbf{coRE} és tancada pel revessat.