- Il compito è costituito da tre esercizi "semplici" di cui due dimostrazioni da imparare a memoria, un esercizio semplice, uno medio e uno più difficile.
- Ogni esercizio vale 6 punti, indipendentemente dalla difficoltà
- Quando si dimostra qualcosa è possibile appoggiarsi a teoremi già dimostrati nel libro, a patto di citarli correttamente, o per nome (es. ADFA) oppure usando una descrizione non ambigua (es. Il teorema che dimostra la riconoscibilità di un DFA)
- Ci sono tre tipi di strumento per la decidibilità: uno è A (riconoscibilità), che accetta un automa e una stringa, e due sono E (emptiness) e EQ (equivalenza, solo per linguaggi regolari), che accettano solo un automa. Quindi se non sono specificate stringhe, cioè la richiesta non riguarda la riconoscibilità, ma la decidibilità, bisogna usare gli operatori di unione, concatenamento, star e intersezione, complemento se supportati (no CFG) in maniera furba per arrivare ad applicare o E oppure EQ.
- La definizione di Σ spesso può non essere esplicita. Se va esplicitato, si può scrivere un'espressione che contiene:
x where x ∈ {Σ \ 1}
per indicare 1 o un altro simbolo qualunque - Spiegare brevemente a parole la dimostrazione, in modo che in caso di errori sia chiaro il ragionamento sottostante.
- Non troveremo rice, perché renderebbe troppo semplice la riducibilità
- Non troveremo ATM non è decidibile, perché è troppo lungo per un compito (metodo diagonale di Cantor)