|
Schedule
Lectures: 11:15-13:00, room 402
Practica: 13:45-15:30 room 402 |
Goal
The course gives an introduction is an introduction to the theory of computation with emphasis on the relationships between formal languages, automata and abstract models of computation.
Description
Automata theory and formal languages form the foundations of theoretical computer science, as they allow us to talk precisely about what is an algorithm or a computation.
An automaton is in fact a model of computation that can be defined mathematically. The simplest model that we will consider in this course is given by finite state automaton: a machine that is only able to keep track of its current state but it has no memory. Finite state automata specify an algorithmic procedure for recognizing whether a word is in a language. We will concentrate on the relationships between language recognized by a finite state automaton, language generated by a grammar and language described by a specification, and will obtain algorithms for translating one description of a language into another description of a different type.
Adding restricted form of memory to finite state automata increase their expressivity. We will study push-down automata, i.e. the class of automata with an auxiliary memory organized as a stack. In particular we will concentrate on the class of languages recognized by push-down automata, because of its major role in compiler design and parsing.
Literature
Schedule Lectures
| Nun | Date | Topic | Reading | Exercises |
| 1a | 5 sept | Overview and motivation | ||
| 1b | Languages | [Mar10]:1.4 | Chapter 1 | |
| 1c | Finite Automata | [Mar10]:2.1 | Chapter 2 | |
| 2a | 12 sept | Automata constructions | [Mar10]:2.2 | Chapter 2 |
| 2b | Distinguishability | [Mar10]:2.3 | Chapter 2 | |
| 3a | 19 sept | Minimal FA | [Mar10]:2.5, 2.6 | Chapter 2 |
| 3b | Pumping lemma for RL | [Mar10]:2.4 | Chapter 2 | |
| 4a | 26 sept | Regular Expressions (RE) | [Mar10]:3.1 | Chapter 3 |
| 4b | Non-deterministic automata (NFA) | [Mar10]:3.2 | Chapter 3 | |
| 3 oct | No lesson | |||
| 5a | 10 Oct | From NFA to FA | [Mar10]:3.3 | Chapter 3 |
| 5b | From RE to NFA | [Mar10]:3.4 | Chapter 3 | |
| 6 | 17 Oct | From FA to RE | [Mar10]:3.5 and State removal method | Chapter 3 |
| 7a | 24 Oct | Context free grammars (CFG) | [Mar10]:4.1,4.2 | Chapter 4 |
| 7b | Regular grammars | [Mar10]:4.3 | Chapter 4 | |
| 8a | 31 Oct | Ambiguity | [Mar10]:4.4 | Chapter 4 |
| 8b | Chomsky normal form | [Mar10]:4.5 | Chapter 4 | |
| 9 | 21 Nov | Pushdown automata (PDA) | [Mar10]:5.1, 5.2 | Chapter 5 |
| 10a | 28 Nov | From CFG to PDA | [Mar10]:5.3 | |
| 10a | From PDA to CFG | [Mar10]:5.4 | ||
| 11b | Pumping lemma for CFL | [Mar10]:6.1 | Chapter 6 | |
| 12a | 12 Dec | Intersection and complement of CFL | [Mar10]:6.2 | Chapter 6 |
| 12b | Decision problems for CFL | [Mar10]:6.3 | Chapter 6 |
Bibliography
[Mar10] John C. Martin, Introduction to Languages and the Theory of Computation, 4th Revised edition, McGraw Hill Higher Education, 2010.
Past Examinations
- January 2004 and August 2004
- January 2005 and August 2005
- January 2006 and August 2006
- January 2007 and August 2007
- January 2008 and August 2008
- January 2009 and August 2009
- January 2010 and August 2010
- January 2011 and August 2011