## Courses Catalogue

We welcome you to explore NOVA’s academic offerings.
Our catalogue provides a description of the courses offered at NOVA as well as useful information about our Schools.

# Theory of Computation

2468

### Department

Departamento de Informática

6.0

### Teacher in charge

Luís Fernando Lopes Monteiro

5

70

Português

### Objectives

Objectives

Knowledge
• 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.

Know-how
• 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.

Soft-Skills
• 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

1. Languages
1. Basic notions: symbol, alphabet, word, language
2. Regular languages and regular expressions
2. Finite Automata
1. Deterministics and nondeterministic finite automata
2. Regular expressions and finite automata
3. Iteration property and nonregular languages
4. Reduced automata
3. Grammars
1. Chomsky''s classification
2. Context-free grammars
3. Derivation trees and ambiguity
4. Reduced grammars
5. Chomsky''s normal form
6. Iteration property
4. Pushdown automata
1. Acceptance criteria
2. Deterministic pushdown automata
3. Generalized  pushdown automata
4. Relationship with context-free grammars
5. Parsing
1. Top-down parsing: LL(1) grammars
2. Bottom-up parsing: LR(0) and LR(1) grammars
6. Turing machines
1. Turing machine models
2. Recursive and recursively enumerable languages
3. Church-Turing thesis
4. Undecidability of the halting problem
5. Undecidable problems for context-free grammars
7. Program verification
1. Floyd''s inductive assertions method
2. Introduction to Hoare''s axiomatic method

### Bibliography

#### Course handouts

• Lecture notes.
• Slides.
• Class problems.
• Solved problems

#### Recommended bibliography

The two following books are recommended:
• 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

#### 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%).