Faculty of Computer Science

Bachelor in Applied Computer Science

Formal Languages

**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.

**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.

teaching page of Diego Calvanese