Faculty of Computer Science

Bachelor in Applied Computer Science

Formal Languages

**1/10/2008**: The results of the final exam of 26/9/2008 are available.

Students interested in getting an insight into their exam and the corrections can come to the office hours on Friday 3/10/2008 at 15:00 in my office. After that date, the marks will be finalized.

Please note that my office is now in the new building of the Faculty of Computer Science, via della Mostra, 4, office 2.08.

**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. 2007. 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 8th 2007
to January 19th 2008.
**Lectures**: Monday, 8:30-10:30, Seminar Room E221, 2nd floor, Ser E (typically)**Exercises**: Monday: 14:00-15:00, , Seminar Room E221, 2nd floor, Building E

Some lectures and exercises have been rescheduled, as specified here (lectures and exercises that are outside the regular schedule are marked in yellow).

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
- exam esercises (in part with solutions) from the Theory of Computing course. Part 1 of these exams covers the same topics as the Formal Languages course, although at a deeper level.

teaching page of Diego Calvanese