Computational Models
Keywords |
Classification |
Keyword |
OFICIAL |
Computer Science |
Instance: 2019/2020 - 2S ![Requerida a integração com o Moodle Ícone do Moodle](/fcup/pt/imagens/MoodleIcon)
Cycles of Study/Courses
Teaching language
Portuguese
Objectives
Teach fundamental concepts and results about three computational models (finite automata, pushdown automata, Turing machines) and the related classes of formal languages, with emphasis on regular and context free languages.
Learning outcomes and competences
Students are expected to be able to describe simple formal languages using different models of computation and classify them in the Chomsky hierarchy.
Working method
Presencial
Program
Notion of formal language. Deterministic finite automata and non-deterministic finite automata. Regular expressions and finite automata. Properties of regular languages. Minimization of finite automata. Pumping lemma for regular languages. Context-free grammars and languages. Derivation trees. Ambiguity. Simplification of context-free grammars and normal forms. Push-down automata. Properties of context-free languages. Pumping lemma for context-free grammars. Turing machines and notion of computability.
Mandatory literature
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman; Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2006. ISBN: 0-321-47617-4
Dexter C. Kozen; Automata and Computability, Sringer, 1997. ISBN: ISBN 0-387-94907-0
Mark V. Lawson; Finite Automata, Chapman & Hall/CRC, 2004. ISBN: 1-58488-255-7
Teaching methods and learning activities
Lectures: exposition of the syllabus topics and examples.
Practical Lectures: exercise solving and discussion.
Evaluation Type
Distributed evaluation without final exam
Assessment Components
designation |
Weight (%) |
Teste |
100,00 |
Total: |
100,00 |
Amount of time allocated to each course unit
designation |
Time (hours) |
Estudo autónomo |
56,00 |
Frequência das aulas |
106,00 |
Total: |
162,00 |
Eligibility for exams
Students must attend at least 3/4 of the pratical classes to be admitted to the exams.
Calculation formula of final grade
The final mark corresponds to the classification obtained
- as average grade of three tests to be realized during the semester and at the date of the first exam (each with a classification of at least 6 out of 20 points);
- or the grade of the second exam (época de recurso).
Classification improvement
Distributed evaluation (3 tests) without final exam.