Automi calcolabilità e complessità

Tratta di come si modella la computazione e dei limiti della computazione. Materiale del corso, Libro.

Modalità d’esame

Esame strutturato in 3 parti:

• Automi
• Calcolabilità
• Complessità

Ogni parte ha 1 esercizio e una domanda di teoria.

Libro di testo: Sipser, Introduzione alla teoria della computazione.

Argomenti

• automa
  • automa deterministico a stati finiti (DFA)
  • configurazione
  • linguaggio regolare
  • Star di Kleene
  • non determinismo
  • automa non deterministico a stati finiti (NFA)
  • espressioni regolari (regex)
  • forma canonica degli NFA
  • Generic Non deterministic Finite state Automaton (GNFA)
  • grammatica acontestuale (CFG)
    • forma normale di Chomsky
  • automa a pila (PDA)
  • equivalenza tra PDA e CFG
• calcolabilità
  • (TM) macchina di Turing
  • problemi NP completi
  • teoria dell’incompletezza di Godel
  • teoria dell’indecidibilità di Turing
• complessità (P vs NP)