ALF Automi Linguaggi Formali Esercizi-Aiuto

[mitch95]

Salve, qualcuno potrebbe aiutarmi con questi esercizi? Sono veramente indeciso su quali siano le affermazioni corrette.

-Si consideri il seguente insieme'

A = {n ≤ 100 | dom([size=150]φ[/size][size=50]n[/size]) infinito}

Individuare tra le seguenti le affermazioni vere.
Scegli una o più alternative:
a. A è ricorsivo
b. A è semanticamente chiuso
c. A è ricorsivamente enumerabile
d. il complemento di A è ricorsivamente enumerabile
e. A non è ricorsivamente enumerabile

-Si consideri il seguente insieme:

A = {n | ∃k : [size=150]φ[/size][size=50]k[/size] (n)↑}

Individuare tra le seguenti le affermazioni vere.
Scegli una o più alternative:
a. A è ricorsivo
b. A è semanticamente chiuso
c. A è ricorsivamente enumerabile
d. il complemento di A non è ricorsivamente enumerabile
e. A non è ricorsivamente enumerabile

-Si consideri il seguente insieme:

A = {n | ∀ x : [size=150]φ[/size][size=50]n[/size] (x)↓}

Individuare tra le seguenti le affermazioni vere.
Scegli una o più alternative:
a. A è ricorsivo
b. A è semanticamente chiuso
c. A è ricorsivamente enumerabile
d. il complemento di A è ricorsivamente enumerabile
e. A non è ricorsivamente enumerabile

-Si consideri il seguente insieme:

A = {n | ¬∃m > n.[size=150]φ[/size][size=50]n[/size] = [size=150]φ[/size][size=50]m[/size]}

Individuare tra le seguenti le affermazioni vere.
Scegli una o più alternative:
a. A è ricorsivo
b. A è semanticamente chiuso
c. A è ricorsivamente enumerabile
d. il complemento di A non è ricorsivamente enumerabile
e. A non è ricorsivamente enumerabile

[gugo82]

Idee tue?