Faculty of Computer Science

Bachelor in Applied Computer Science

Formal Languages

**3/3/2012**: The results of the final Formal Languages exam of 16/7/2012 are available.

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.

[M3]JFLAP - An Interactive Formal Languages and Automata Package. Susan H. Rodger, Thomas W. Finley. Jones and Bartlett Publishers, 2006.

*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: Babak
Bagheri Hariri (follow the link for the office hours)
- Schedule: The course is taught in the 1st semester: from October 7th 2010
to January 21st 2011.
**Lectures**: Thursday, 8:30-10:30, Seminar Room D003, ground floor, Sernesi D**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