⟸ pàgina anterior ⟸

Exercici 5 (Tasca 5).

(R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, homomorphism, inverse homomorphism)

\mathbf{R}, \mathbf{RE} i \mathbf{coRE}, i els homomorfismes

L’objectiu d’aquest exercici és investigar com es comporten les classes \mathbf{R}, \mathbf{RE} i \mathbf{coRE} per homomorfisme i homomorfisme invers.

Nota

Recordeu també que una classe de llenguatges \cal C és tancada per homomorfisme si per tot llenguatge A \in {\cal C} i homomorfisme \sigma, \sigma(A) \in {\cal C}. També, {\cal C} és tancada per homomorfisme invers si per tot llenguatge A \in {\cal C} i homomorfisme \sigma, \sigma^{-1}(A) \in {\cal C}.

1. Homomorfisme.

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

2. Homomorfisme invers.

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