| Cosa | ∪ | ○ | * | ∩ | ¬ | A | E | EQ |
|---|---|---|---|---|---|---|---|---|
| DFA | Chiuso (1.25 [prodotto cartesiano] oppure 1.45 [equivalenza con NFA]) | Chiuso (1.47 [equivalenza con NFA]) | Chiuso (1.49 [equivalenza con NFA]) | Chiuso (1.25 [prodotto cartesiano]) | Chiuso (Esercizio 1.14a) | sì (4.1): simulando un DFA in una TM si ottiene accept o reject | sì (4.4.): marcare gli stati del DFA ricorsivamente | sì (4.5): verificare che la differenza simmetrica dei due DFA sia vuota |
| NFA | Chiuso (1.45) | Chiuso (1.47) | Chiuso (1.49) | Chiuso (1.25 [equivalenza con DFA]) | Chiuso (Esercizio 1.14b) | sì (4.2): convertire un NFA in un DFA e applicare ADFA | ||
| REX | Chiuso (definizione 1.52) | Chiuso (definizione 1.52) | Chiuso (definizione 1.52) | Chiuso (equivalenza con DFA) | Chiuso (equivalenza con DFA) | sì (4.3): convertire REX in NDA e applicare ANFA | ||
| CFG | Chiuso (esercizio 2.16) | Chiuso (esercizio 2.16) | Chiuso (esercizio 2.16) | Non chiuso (esercizio 2.2) | Non chiuso (esercizio 2.2) | sì (4.7): convertire il CFG in forma normale di Chomsky, elencare le derivazioni e verificare w | sì (4.8): marcare i terminali ricorsivamente | no (4.8): poiché i CFG non sono chiusi per intersezione e complemento. |
| PDA | ||||||||
| Linguaggi decidibili | Chiuso (esercizio 3.15) | Chiuso (esercizio 3.15) | Chiuso (esercizio 3.15) | Chiuso (esercizio 3.15) | Chiuso (esercizio 3.15) | |||
| TM | Chiuso (esercizio 3.16) | Chiuso (esercizio 3.16) | Chiuso (esercizio 3.16) | Chiuso (esercizio 3.16) | No (4.11): metodo della diagonale di Cantor | No (5.2) | No (5.4) |