u n i g e . i t - Informatica a Genova

Corsi di Laurea in Informatica - Computer Science Degrees

DIBRIS - Valle Puggia

  • Full Screen
  • Wide Screen
  • Narrow Screen
  • Increase font size
  • Default font size
  • Decrease font size

80303 - Foundations of Computer Science (2015/2016) Stampa

Course syllabus

Automata and Languages

Alphabets, strings, languages and their operations
Deterministic finite automata (DFA) and nondeterministic finite automata (NFA)
DFA minimization, regular expressions
Closure properties and pumping lemma for regular languages
Context-free grammars, derivation trees, ambiguity
Push down deterministic and non deterministic automata (PDA)
Equivalence between PDA and context-free grammars
Closure properties and pumping emma for context-free languages
Chomsky hierarchy, context-sensitive languages, semi-decidability and decidability results
Equivalence between finite automata and linear grammars

Turing machines, languages accepted by Turing machines
Nondeterministic Turing machines
Semi-infinite tapes
Other kinds of machines: Multi-stack, Counter Machine
Indecidability, recursive and RE languages, RE non recursive languages, universal language and machine
Halting problem
Indecidable problems on Turing machine, Rice theorem, other indecidable problems
Recursive and primitive recursive functions, total and partial
Complexity (sketch)




Giorgio Delzanno

Elena Zucca


John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman

Introduction to Automata Theory, Languages, and Computation

Teaching style

In presence

Lesson timetable

Monday: 9:00 - 11:00, room 710
Wednesday: 11:00 - 13:00, room 710



Course hour allocation

This course consists of 48 hours of lectures.