Dai temi d’esame:

• Si fornisca la definizione di Automa a Stati Finiti NON deterministico (NFA)
• Si fornisca la definizione di funzione di transizione estesa per gli NFA
• Si fornisca la definizione di espressione regolare con la relativa semantica (linguaggio generato)
• Si fornisca la definizione di derivazione in zero o più passi per le grammatiche libere dal contesto (CFG)
• Si fornisca la definizione di Macchina di Turing e di linguaggio accettato da una macchina di Turing.
• Si fornisca la definizione di linguaggio ricorsivamente enumerabile e decidibile

Altre definizioni che potrebbe chiedere:

• Definizione di Automa a Stati Finiti Deterministico (DFA)
• Definizione di stringa accettata
• Definizione di linguggio accettato
• Definizione di funzione di transizione estesa per i DFA
• Definizione di linguaggio regolare
• Definizione di $\epsilon$-NFA
• Definizione di $\epsilon$-chiusura di uno stato
• Definizione di chiusura e chiusura positiva di Kleene
• Definizione di Pumping Lemma (per i linguaggi regolari)
• Definizione di complemento di un linguaggio
• Definizione di inverso di una stringa e di un linguaggio
• Definizione di reverse di un’espressione regolare