Free University of Bolzano/Bozen
Faculty of Computer Science
Bachelor in Applied Computer Science
Formal Languages
Preliminary Program A.Y. 2010/2011
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:
Monday, 13-Sep-2010 0:19:59 CEST