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
 Computability

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)

Language

Italian

Teacher

Giorgio Delzanno

Elena Zucca

Textbooks

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

Attendance

Suggested

Course hour allocation

This course consists of 48 hours of lectures.