Theory of Computation
Faculdade de Ciências e Tecnologia
Departamento de Informática
Teacher in charge
Luís Fernando Lopes Monteiro
To know the basic elements of the theories of fomal languages and automata, including the parsing of languages.
To know the bases on which the formal concept of algorithm is founded and the existence of problems without algorithmic solution.
To know the role of logic as a tool to reason about imperative programs.
To manipulate the formalisms of automata and grammars for several purposes, in particular for the construction of parsers.
- To design Turing machines for simple problems.
To reason formally and informally about correction and termination properties of programs in a simple imperative language.
The course stimulates the capacity to use mathematical abstraction to solve generic problems;
understand and formulate rigorous definitions;
- determine their logical consequences.
Students should have completed before the courses Introduction to Programming and Discrete Mathematics.
- Basic notions: symbol, alphabet, word, language
- Regular languages and regular expressions
- Finite Automata
- Deterministics and nondeterministic finite automata
- Regular expressions and finite automata
- Iteration property and nonregular languages
- Reduced automata
- Chomsky''s classification
- Context-free grammars
- Derivation trees and ambiguity
- Reduced grammars
- Chomsky''s normal form
- Iteration property
- Pushdown automata
- Acceptance criteria
- Deterministic pushdown automata
- Generalized pushdown automata
- Relationship with context-free grammars
- Top-down parsing: LL(1) grammars
- Bottom-up parsing: LR(0) and LR(1) grammars
- Turing machines
- Turing machine models
- Recursive and recursively enumerable languages
- Church-Turing thesis
- Undecidability of the halting problem
- Undecidable problems for context-free grammars
- Program verification
- Floyd''s inductive assertions method
- Introduction to Hoare''s axiomatic method
- Lecture notes.
- Class problems.
- Solved problems
- Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, Boston, 1997.
Thomas A. Sudkamp, Languages and Machines, Addison-Wesley, 1997. Eitan Gurari, An Introduction to the Theory of Computation , Computer Science Press, 1989. Available online at http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html
The course consists of lectures and problem-solving sessions.
The instructors can be contacted during the office hours but also through e-mail, the discussion forum and repetition sessions.
0 to 20.
-- One mid-semester test (T).
-- Homework to be answered online (O).
-- Final exam (E).
Admission to the final exam
Least grade in the exam
The grade in the exam must be at least 9.5.
If the grade E in the exam is <9.5, the final grade is E.
If E >=9.5, the final grade is
where T counts with 5 at most (25%), O with 2 (10%) and E with the remaining values as the case may be (65%, 75%, 90% and 100%).