This version of the course guide is provisional until the period for editing the new course guides ends.

Logo UAB

Theory of Computation

Code: 107891 ECTS Credits: 6
2025/2026
Degree Type Year
Computer Engineering FB 1

Contact

Name:
Joan Serra Sagrista
Email:
joan.serra@uab.cat

Teachers

Joaquin Borges Ayats

Teaching groups languages

You can view this information at the end of this document.


Prerequisites

Notice on the language of instruction and syllabus translations

The language of instruction for all groups of this course is Catalan.

Automatic translations of the syllabus into English and Spanish are provided for informational purposes only.

In case of any discrepancy or inconsistency between versions in different languages, the Catalan version shall prevail as the official reference.

 

==

 

Although there are no official prerequisites, it is essential that students have a very good command of the most basic notions of mathematics, such as:

- Master the manipulation of mathematical language

- Master proofs by induction and contradiction

- Mastering the ability to abstract

 

Students who do not have a minimum background in previous mathematics will have to make an effort to worry about solving these deficiencies.


Objectives and Contextualisation

-              Sort the properties of the formal models on which computers are based 

-              Identify the possibilities and limits of computing

-              Acquire good programming habits


Learning Outcomes

  1. CM05 (Competence) Integrate computational model-based techniques into computer science problems.
  2. KM09 (Knowledge) Explain algorithmic procedures of computational theory for solving computer engineering problems.
  3. SM13 (Skill) Apply knowledge of automatons, grammars and computational complexity to solve problems.

Content

1. Formal languages and abstract calculation models.

1.1. Alphabets, words and languages.

1.2. Problems, formal languages and calculation models.

1.3. Digital systems.

1.4. Demonstration methods.

 

2. Finite automata and regular languages.

2.1. Deterministic finite automata.

2.2. Non-deterministic finite automata.

2.3. Operations, experiments and regular languages.

2.4. Minimization of the number of internal states.

2.5. Automata with output.

 

3. Context-independent grammars.

3.1. Introduction.

3.2. Definitions. Language generation.

3.3. Simplification of grammars.

3.4. Chomsky and Greibach normal forms.

 

4. Automata with battery.

4.1. Description.

4.2. Acceptance by final state and empty stack.

4.3. Stacked automata and context-independent languages.

4.4. Properties of context-independent languages.

 

5. Turing machines.

5.1. Description of the basic model.

5.2. Computable languages and functions.

5.3. Variants of the Turing machine.

5.4. Church's hypothesis. Von Neumann machine.

5.5. Turing machines as enumerators.

 

6. Undecidability.

6.1. Decidable and undecidable problems and languages.

6.2. Recursive and recursively enumerable languages.

6.3. Universal Turing machine and undecidable problems.

6.4. The Post Correspondence Problem and the Stop Problem.

6.5. Examples of non-recursive languages.

 

7. Computational complexity.

7.1. Introduction. Types of problems.

7.2. Complexity classes.

7.3. NP-Completeness,

7.4. Some NP-Complete problems.

 


Activities and Methodology

Title Hours ECTS Learning Outcomes
Type: Directed      
Theory and Exercises Sessions 50 2 CM05, KM09, SM13, CM05
Type: Supervised      
Exercises 28 1.12 CM05, KM09, SM13, CM05
Type: Autonomous      
Preparation and autonomous work 26 1.04 CM05, KM09, SM13, CM05
Study and preparation of evaluating activities 38.5 1.54 CM05, KM09, SM13, CM05

The sessions will be taught according to the type of Classroom Practices (PAUL): Discussion and realization of exercises and activities in group or individually.

 

The teaching methodology is oriented towards the learning of the subject on a continuous basis. Activities that will be developed throughout the course:

 

• Theory and problem sessions, where teachers will provide information on knowledge and strategies for acquiring, expanding and organising it. The active participation of students will be encouraged. Learning will be monitored through individual and/or group development of validation and achievement activities.

 

Annotation: Within the schedule set by the centre or degree programme, 15 minutes of one class will be reserved for students to evaluate their lecturers and their courses or modules through questionnaires.


Assessment

Continous Assessment Activities

Title Weighting Hours ECTS Learning Outcomes
Exercises delivery and/or validation activities 30 3.5 0.14 CM05, KM09, SM13
Partial Exam 1 35 2 0.08 CM05, KM09, SM13
Partial Exam 2 35 2 0.08 CM05, KM09, SM13

During the course, a series of exercises and/or validation activities will be carried out at the end of each of the topics. The grades of these exercises and/or activities will account for 30% of the final grade. This part of the grade will NOT be recoverable.

There will be an exam (First Partial = P_1) before mid-semester in which the work done up to that moment will be evaluated. The grade of this exam will contribute 35% of the final grade. All students who take this exam can no longer be graded as NON-EVALUABLE Any student who has not taken this exam will be recorded as NOT ASSESSED for academic purposes and will not have the right to retake it (except for duly justified reasons, in which case the retake exam will be allowed).

At the end of the semester there will be a second midterm exam (which we call P_2) in which the knowledge taught after the first partial will be evaluated. The grade of this exam will contribute another 35% of the final grade. Students who have not taken this exam will not be entitled to retake it (except for duly justified reasons, in which case the retake exam will be allowed).

Qualification:

If the average of the grades (out of 10) of the two midterms M=(P_1+P_2)/2 is less than 2.5, the student has failed the subject, with a final grade of M, without the right to go to the retake exam. If M is greater than 2.5 but less than or equal to 3.5, the student must take the retake exam. If M is greater than or equal to 3.5 then if NF=0.7 M + 0.3 S, (where S is the average grade of the delivery of validation exercises and/or activities, out of 10) is greater than or equal to 5 the student has passed and has NF as the final grade, otherwise he/she must go to the retake exam If the student has to take the retake exam, then if the retake grade R is less than 3.5, the student has failed with a final grade R; if R is greater than or equal to 3.5 the final grade will be min({0.7 R + 0.3 S},7) where R is the grade of the retake exam (out of 10). The use of a calculator in the midterm exams and in the retake exam is not allowed. 5% of the highest grades may obtain the Honors grade provided that: the grade of each midterm is not less than 9 and the NF grade described above exceeds 9.1. These evaluation conditions will be the same for all students enrolled in the subject, regardless of whether they are first enrolled or if they had already enrolled in previous years. The final decision on the MH grade will be decided by the teaching staff.

For each assessment activity, a place, date and time of review will be indicated in which the student will be able to review the activity with the teaching staff. In this context, complaints may be made about the grade of the activity, which will be evaluated by the teaching staff responsible for the subject. If the student does not attend this review, this activity will not be reviewed later. The dates of the midterm exams will be published on the Virtual Campus (CV) and may be subject to possible programming changes for reasons of adaptation to possible incidents; the CV will always be informed of these changes since it is understood that the CV is the usual mechanism for exchanging information between lecturer and students.

In this subject, the use of any type of digital device is NOT allowed in the classroom (no computers, tablets, no mobile phones, ...); consequently, the use of Artificial Intelligence (AI) technologies is not allowed in the classroom. Any work done in the classroom that includes fragments generated with AI will be considered a lack of academic honesty and may result in a partial or total penalty in the grade of the activity, or greater penalties in cases of seriousness. The use of Artificial Intelligence (AI) technologies is allowed in autonomous activities outside the classroom. Without prejudice to other disciplinary measures that are considered appropriate and in accordance with current academic regulations, irregularities committed by a student that may lead to a variation in thegrade will be graded with a zero (0). For example, plagiarism, copying, allowing copying, having communication devices (such as mobile phones, smart watches, etc.) in an evaluation activity, will imply failing this evaluation activity with a zero (0). Assessment activities graded in this way and by this procedure will not be recoverable. If it is necessary to pass any of these assessment activities to pass the subject, this subject will be suspended directly, without the opportunity to recover it in the same year. The numerical grade of the transcript will be the lowest value between 3.0 and the weighted average of the grades in the event that the student has committed irregularities in an evaluation act (and therefore it will not be possible to pass by compensation). The assessment of transversal competences is integrated into the rubric (or problem correction guideline) of the midterm exams. The score of the sections of the rubric corresponding to transversal competences has a value of between 5% and 10% of the score of the corresponding problem. This subject does not contemplate a differentiated treatment for repeating students.

This subject does not provide for the single assessment system.


Bibliography

PRIMARY REFERENCES

Borges, J.; Serra, J i Arqués, J. M. (1996). Teoria d’autòmats. Materials 28, Publicacions de la UAB.

AUXILIARY REFERENCES 

Casas, R. i Màrquez, L. (2000). Llenguatges, gramàtiques i autòmats. Curs bàsic. Aula teòrica 41, UPC.

Hopcroft, J. E.; Motwani, R. and Ullman, J. D. (2002). Introducción a la teoría de autómatas, lenguajes y computación. Addison Wesley.

(https://docencia.eafranco.com/materiales/teoriacomputacional/books/TeoriaDeAutomatas,lenguajesYComputacion-Hopcroft.pdf)

Linz, P. (2001). An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers.

Martin, J. C. (2004) [2003]. Lenguajes formales y teoría de la computación. McGraw-Hill Interamericana.


Software

There are no Laboratory Practices; In principle, we will not use any software.


Groups and Languages

Please note that this information is provisional until 30 November 2025. You can check it through this link. To consult the language you will need to enter the CODE of the subject.

Name Group Language Semester Turn
(PAUL) Classroom practices 411 Catalan second semester morning-mixed
(PAUL) Classroom practices 412 Catalan second semester morning-mixed
(PAUL) Classroom practices 431 Catalan second semester morning-mixed
(PAUL) Classroom practices 432 Catalan second semester morning-mixed
(PAUL) Classroom practices 451 Catalan second semester afternoon
(PAUL) Classroom practices 452 Catalan second semester afternoon