Theory of Computation

Code:

L.EIC010

Acronym:

TC

Keywords
Classification	Keyword
OFICIAL	Informatics Engineering and Computing

Instance: 2024/2025 - 2S

Active?	Yes
Web Page:	https://moodle2324.up.pt/course/view.php?id=5619
Responsible unit:	Department of Informatics Engineering
Course/CS Responsible:	Bachelor in Informatics and Computing Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L.EIC	385	Syllabus	1	-	6	52	162

Teaching language

Suitable for English-speaking students

Objectives

To prepare students about computing theory topics with a special emphasis on formal language topics.

Students will learn about regular languages, regular expressions, non-regular languages, deterministic and nondeterministic finite automata, context-free languages and grammars, deterministic and non-deterministic pushdown automata, and Turing machines, and how to apply these topics to problems.

Students will be able to express computing problems by using formal languages, automata, and Turing machines.

In addition, students will learn how to formally specify computing problems related to formal languages and prove related statements.

Learning outcomes and competences

At the end of the semester, students should:
- Be capable of identifying the important contributions to computing theory and its protagonists;
- Be capable of identifying the problems that can be solved with finite automata and express them rigorously;
- Be capable of comparing deterministic finite automata (DFAs), non-deterministic finite automata (NFAs), regular expressions, and regular languages;
- Be capable of applying the properties of regular languages;
- Be capable of identifying problems that can be handled by context-free grammars (CFGs);
- Be capable of relating context-free grammars and pushdown automata (PDAs) in the processing of context-free languages;
- Be capable of expressing computing problems by using Turing machines;
- Be capable of relating the studied computing models with their applications in the computability theory and complexity theory.

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

It is recommended that students have attended the Discrete Mathematics course.

Program

Notions of formal languages. Automata Theory; Finite Automata;

Regular Expressions and Languages;

Properties of Regular Languages;

Automata minimization and pumping lemma;

Context-Free Grammars and Languages;

Pushdown Automata;

Properties of Context-Free Language;

Introduction to Turing Machines.

Mandatory literature

John E. Hopcroft; Introduction to automata theory, languages, and computation. ISBN: 978-1-292-03905-3

Complementary Bibliography

Hopcroft, John E.; Introdução à teoria de autômatos, linguagens e computação. ISBN: 85-352-1072-5
Sipser, Michael; Introduction to the theory of computation. ISBN: 0-619-21764-2
Sudkamp, Thomas A.; Languages and Machines. ISBN: 0-201-15768-3

Teaching methods and learning activities

In lectures, the contents are formally exposed along with presentation and discussion of examples.
In the tutorial classes, application exercises are proposed.
Weekly, the students are asked to do exercises to check if the basic concepts are being understood by the majority of students.
The foreseen effort beyond classes is about 4h per week.

Software

JFLAP is software for experimenting with formal languages topics. (https://www.jflap.org/)
https://automata-tutor.model.in.tum.de/index
http://turingmachine.io/
https://pypi.org/project/fado/

keywords

Physical sciences > Computer science
Physical sciences > Mathematics > Computational mathematics

Evaluation Type

Distributed evaluation without final exam

Assessment Components

Designation	Weight (%)
Teste	90,00
Trabalho prático ou de projeto	10,00
Total:	100,00

Amount of time allocated to each course unit

Designation	Time (hours)
Estudo autónomo	103,00
Frequência das aulas	59,00
Total:	162,00

Eligibility for exams

A maximum of 3 absences (25%) on the tutorial classes.

Calculation formula of final grade

Two written tests will be carried out, each with a weight of 45% of the final grade, the second being during the normal exam period. 

Moreover, in some TP classes the students will solve an exercise that will be evaluated. The total grade of these exercises will amount for 10% of the final grade.

Final grade of continuous assessment: 10% exercise + 45 test1 + 45 test2

Final exam grade: 100% exam.

Examinations or Special Assignments

None.

Special assessment (TE, DA, ...)

For TE students, two written tests will be carried out, each with a weight of 50% of the final grade, the second being during the normal exam period. Students will have to obtain in each test a minimum grade of not less than 6 values (out of 20).

Final grade of continuous assessment: 50% test1 + 50% test2

Final exam grade: 100% exam.

Classification improvement

The final grade can be improved with a classification improvement exam (implies a registration to improve the grade in the course). In the case of improvement, the grade of the exam will be the final grade of TC.