Home page of the course
Formal Languages

News

• 3/10/2009: The results of the final exam of 11/9/2009 are available.
  There will be an office hour on Tuesday 6/10/2009 at 17:30 in my office in via della Mostra 4, where students can discuss their exam and the corrections. After that date, the marks will be finalized.
  

Course presentation form

Objectives. The objective of the Formal Languages course is to introduce and study the basic abstract models of computation, namely finite state machines, push down machines, and formal grammars, and their relationships to formal languages encoding problems. It is also discussed how the abstract computing devices are used to process languages, and hence to solve problems that are of practical relevance. A second objective is to get the student acquainted to a formal, rigorous approach in computer science.

Prerequisites. There are no prerequisites in terms of courses to attend. Students should be familiar with the basic notions of mathematics and set theory as taught in the mathematics courses of the first year.

Teaching material

[M1] Introduction to Automata Theory, Languages, and Computation (3rd edition). J.E. Hopcroft, R. Motwani, J.D. Ullman. Addison Wesley, 2007.
[M2] Lecture Notes for Formal Languages. Diego Calvanese. 2008. Available on the course web page as scanned pages in pdf.

• Elements of the Theory of Computation (2nd edition). H.R. Lewis, C.H. Papadimitriou. Prentice Hall. 1998.
• Introduction to the Theory of Computation. M. Sipser. PWS Publishing Company. 1997.

• Office hours

• Teaching assistant: Kurt Ranalter (follow the link for the office hours)

• Schedule: The course is taught in the 1st semester: from October 9th 2008 to January 29th 2009.
  • Lectures: Thursday, 8:30-10:30, Seminar Room E411, 4th floor, Sernesi E (typically)
  • Exercises: Thursday, 15:00-16:00, Seminar Room E420, 4th floor, Sernesi E
    

  See also RIS calendar for changes.
  

• Additional teaching material
  • Lecture notes (made available during the course)
  • Esercises solved in class (made available during the course)

• Exams
  • Course program
  • Collection of exam exercises.
  • Previous exams.