Theory of Computation
Code
2468
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Informática
Credits
6.0
Teacher in charge
Luís Fernando Lopes Monteiro
Weekly hours
5
Total hours
70
Teaching language
Português
Objectives
Objectives
-
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.
Prerequisites
Students should have completed before the courses Introduction to Programming and Discrete Mathematics.
Subject matter
- Languages
- 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
- Grammars
- 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
- Parsing
- 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
Bibliography
Course handouts
- Lecture notes.
- Slides.
- Class problems.
- Solved problems
Recommended bibliography
- 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
Teaching method
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.
Evaluation method
Grading scale
0 to 20.
Assessment items:
-- One mid-semester test (T).
-- Homework to be answered online (O).
-- Final exam (E).
Admission to the final exam
No requirements.
Least grade in the exam
The grade in the exam must be at least 9.5.
Final grade
If the grade E in the exam is <9.5, the final grade is E.
If E >=9.5, the final grade is
MAX(T+O+E,T+E,O+E,E)
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%).