### Free University of Bolzano/Bozen

Faculty of Computer Science

Bachelor in Applied Computer Science

# Formal Languages

# Final Program A.Y. 2009/2010

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

**Basic notions** [M1: Chapter 1]
- basic notions about relations, functions, and their properties
- basic notions about formal languages

**Finite state automata** [M1: Chapter 2]
- deterministic finite automata
- non-deterministic finite automata
- finite automata with epsilon-transitions

**Regular expressions** [M1: Chapter 3]
- properties of regular expressions
- relationship between regular expressions and finite automata

**Properties of regular languages** [M1: Chapter 4]
- closure properties of regular languages
- proving languages not to be regular
- decision problems for regular languages
- minimizing finite state automata

**Chomsky grammars and context-free languages**
- classification of grammars [M2]
- context-free grammars [M1: Chapter 5]
- normal forms for context-free grammars [M1: Section 7.1]

course home page

*Last modified:
Saturday, 3-Jul-2010 13:47:51 CEST
*