Faculty of Computer Science

Bachelor in Applied Computer Science

Formal Languages

**29/9/2010**: The results of the final Formal Languages exam of 13/9/2010 are available.

There will be an office hour on Friday 1/10/2010 at 15:00 in my office in piazza Domenicani 3 (2nd floor), where students can discuss their exam and the corrections. After that date, the marks will be finalized.

Course presentation form (available also as a pdf file)

**Objectives.** The main objective of the Formal Languages course is to
introduce the fundamental notions about formal languages and the mechanisms for
representing them. The course will focus on the formal languages that find most
applications in computer science, namely regular and context-free
languages. Students should become familiar with the fundamental representation
mechanism for such languages, which span machine-based models (finite state
machines for regular languages), algebraic models (regular expressions), and
generation-based models (formal grammars). The aim is to exploit such
representation mechanisms to study the properties of the different types of
formal languages and the main algorithms for processing languages, which help
to solve problems that are of practical relevance. A second objective of the
course is to get students 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 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. 2009. 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: The exercise hours are taught by the lecturer.
- Schedule: The course is taught in the 1st semester: from October 5th 2009
to January 23th 2010.
**Lectures**: Wednesdya, 8:30-10:30, Seminar Room E420, 4th floor, Sernesi E (typically)**Exercises**: Friday, 8:30-9:30, 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)
- JFLAP Software Tools for experimenting with formal languages topics. A tutorial for JFLAP is available here.

**Exams**- Course program
- Collection of exam exercises.
- Previous exams.

teaching page of Diego Calvanese