Formal Languages and Automata Theory

Introduce the concepts of automata theory and formal languages, and study their applications. In the subject the students will learn different models of computational machines, grammars and formal languages, as well as the correspondence among automatons, languages and grammars. Also, the concepts of decidability and computational complexity will be studied.

Theoretical program

1. Introduction: formal languages, grammars, automata


2. Finite automata

Determinist Finite Automata (DFA)
Nondeterministic Finite Automata (NFA)
Transformation of NFA to DFA
Minimization of DFA


3. Regular languages

Regular expressions
Finite Automata and regular expressions
Algebraic laws for regular expressions
Pumping lemma for regular languages


4. Context-free grammars (CFG)

Definition of grammars
Derivations
Parse trees
Ambiguity
Normal forms for CFG


5. Pushdown Automata

Nondeterministic pushdown automata
Acceptance by empty stack and final state
Transformation of grammars to pushdown automata
Deterministic pushdown automata
Pumping lemma for context-free languages (CFL)


6. Turing Machines

Basic Turing machine
Extensions to the basic Turing machine
Restricted Turing machines


7. Decidibility and complexity

Recursive and recursively enumerable languages
Undecidable Problems
Intractable Problems: the classes P and NP
NP-complete problems


Practical program

The practical lectures are divided in three blocks:

1. Finite state automata and regular expressions

2. Pushdown automata and context-free grammar

3. Turing machines

Basic

LINZ, Peter. Introduction to formal languages and automata. Ed. 3, Boston: Jones and Bartlett Publishers, 2006. ISBN 978-0-7637-3798-6.

HOPCROFT, John E., MOTWANI, Rajeev, ULLMAN, Jeffrey D. Teoría de Autómatas, Lenguajes y Computación. Ed. 3, Madrid: Pearson Educación, 2008. ISBN 978-84-7829-088-8.


Complementary

ALFONSECA CUBERO, Enrique, ALFONSECA MORENO, Manuel, MORIYÓN SALOMÓN, Roberto. Teoría de Autómatas y Lenguajes Formales. Ed. 1, Madrid: McGraw Hill, 2007. ISBN 978-84-481-5637-4.

SUDKAMP, Thomas A. Languages and machines: an introduction to the theory of computer science. Ed. 3, Boston: Pearson, 2006. ISBN 978-0-321-32221-0.

The skills developed in this subject are grouped into 4 blocks (BC), indicating for each of them the associated skill codes for the Degree in Computer Engineering:


(BC1) Models of computation. To know and to understand the capacity that provide various abstract models of computation [specific competence].


(BC2) Decidability and complexity. Ability to understand and master the basics of computational complexity, and its application to solving problems of engineering [FB3]. Knowledge and application of basic algorithmic procedures for computing technologies to design solutions to problems, analyzing the appropriateness and complexity of the proposed algorithms [RI6]. To know and to understand the foundations and limits of computing, and so the existence of computable and non-computable problems, and among the first, the existence of tractable and intractable problems [specific competence].


(BC3) Problem solving. Ability to solve problems with initiative, decision making, autonomy and creativity [CG9]. Capacity for analysis and synthesis; problem solving[TR1].


(BC4) Creativity [TR3].

Theoretical lectures

The professor will elaborate material to study for each of the lessons. In this way, the student can follow each of the lectures. The slides also contain problems. Some of them will be explained during the lecture, while others must be solved by the student during his personal studying time. Most of the exercises have been extracted from previous years exams.


Practical lectures.

The practical sessions will last 2 hours and, during the course, 12 bulletins will be proposed. Before each practice, it is essential to study the corresponding theory. Moreover, it is also advisable that the student tries to solve by his own some of the exercises that have been set out during the theoretical lectures.


The BC1 (computer models) skill will be addressed in all subject topics. Students will know and understand the different models of computation: finite state automata, pushdown automata, linear bounded automata, and Turing machines. Furthermore, they will also study different grammars: regular, context-free, context-sensitive and unrestricted.

The BC2 (decidability and complexity) skill will be tackled in the last block of the subject: Turing machines, decidability and complexity. To do this, students will know and understand the foundations and limits of computation, and thus the existence of computable and non-computable problems, and among the first, the existence of tractable and intractable problems.


The BC3 (problem solving) skill will be addressed on all topics of the course, except the introduction. Much of the theoretical content to be studied throughout the course will be applied to problem solving. Similarly, most practices bulletins consist of a series of problems that students must solve (design of automata and grammars, pumping lemma, etc..). Therefore, for the study of the subject we will foster the autonomous learning of the student through the solution of problems proposed by the teacher, or those included in the recommended bibliography.


The BC4 (creativity) skill will be held on topics about the design of automata or grammars, and also in the application of the pumping lemma. A high percentage of problems / practices that arise in the course require a certain amount of creativity. For instance, the design of various types of automata (finite state, pushdown, Turing machines) and grammars, or even applying the pumping lemma. Creativity is a competence that the learner needs to, must, and can work solving exercises and making practices.


Activities plan.

Lectures:

1. Chapter 1. Introduction.
2. Chapter 2. Finite automata: deterministic finite automata (DFA).
3. Chapter 2. Finite Automata: non-deterministic finite automata (NFA).
4. Chapter 2. Finite Automata: NFA (continued).
5. Chapter 2. Finite Automata: transformation of DFA to NFA.
6. Chapter 2. Finite Automata: minimization of DFA.
7. Chapter 3. Regular languages: regular expressions.
8. Chapter 3. Regular languages: finite automata and regular expressions.
9. Chapter 3. Regular languages: finite automata and regular expressions (continued).
10. Chapter 3. Regular languages: algebra of regular expressions.
11. Chapter 3. Regular languages: pumping lemma for regular languages.
12. Chapter 4. Context-free grammars (CFG): definition of grammars.
13. Chapter 4. Context-free grammars (CFG): derivations.
14. Chapter 4. Context-free grammars (CFG): parse trees; ambiguity.
15. Chapter 4. Context-free grammars (CFG): normal forms for CFG.
16. Chapter 4. Context-free grammars (CFG): normal forms for CFG (continued).
17. Chapter 5. Pushdown automata: non-deterministic pushdown automata.
18. Chapter 5. Pushdown automata: acceptance by empty stack and final state; transformation of grammars to pushdown automata.
19. Chapter 5. Pushdown automata: deterministic pushdown automata; pumping lemma for context-free languages (CFL).
20. Chapter 6. Turing machines: basic Turing machine.
21. Chapter 6. Turing machines: basic Turing machine (continued).
22. Chapter 6. Turing Machines: extensions to the basic Turing machine.
23. Chapter 6. Turing Machines: restricted Turing machines.
24. Chapter 7. Decidability and complexity: recursive and recursively enumerable languages.
25. Chapter 7. Decidability and complexity: undecidable problems; intractable problems: the P and NP classes; NP-complete problems


Interactive sessions:

1. Design of finite state automata.
2. Real applications of finite state automata.
3. Minimization of finite state automata and regular expressions.
4. Pumping Lemma for regular languages.
5. Design of context-free grammars.
6. Design of context-free grammars and Chomsky Normal Form.
7. Design of pushdown automata by final state.
8. Design of pushdown automata by empty stack.
9. Pumping Lemma for context-free languages.
10. Design of standard Turing machines (i).
11. Design of standard Turing machine (ii).
12. Design of context-sensitive grammars (CSG) and unrestricted grammars (URG).

The assessment of the subject will be done in two parts: continuous assessment and final exam. To pass the course, it is compulsory to pass both parts separately.

The continuous assessment will be done with the submission of the practices bulletins of each of the practical sessions, together with a weekly test with questions related to the submitted bulletin. These tests will be carried out in person during the practical classes. All the bulletins will have the same weight in the continuous assessment. The maximum weight of the practices bulletins will be 7 points. Moreover, in the semester, three partial exams will be done. This set of partial exams will increment the grade of the continuous assessment up to 1 point per exam. The maximum grade of the continuous assessment will be 10 points.

In the final written exam the student can get up to 10 points.

The final grade of the subject will be the arithmetic mean of the continuous assessment and the final exam. This is not applied in those cases in which any of the two parts has been failed: in this case the grade will be the minimum of the continuous assessment and the final exam.

The submission of any of the practices bulletins or any of the continuous assessment exams will mean that the student takes the subject. Therefore, from that moment, not attending the final exam will mean that the student fails the course.

In July exams, the continuous assessment grade will be the one obtained in the semester. Students will need to do a new final exam, since the grade of the previous final exam will not be kept.

In the case of fraudulent exercises or tests, the provisions of the regulations on the evaluation of students' academic performance and the review of grades will apply (https://www.xunta.gal/dog/Publicados/2011/20110721/AnuncioG2018-190711-…). In application of the ETSE regulations on plagiarism (approved by the Xunta da ETSE on 19/12/2019), the total or partial copy of any practical or theoretical exercise will result in the suspension of the two opportunities of the course, with a grade of 0.0 in both cases (https://www.usc.es/etse/files/u1/NormativaPlagioETSE2019.pdf).

The skills assessment will be made in the following practices / exams:

[EC1] All practices and exams.
[FB3, RI6, CE2] Practices 10-12 and final exam.
[CG9, TR1] All practices and exams.
[TR3] All practices (except 3) and exams.

The study time of the student for the course along the semester can be divided in the following way:

(1) 25 hours of theoretical lectures (2h/week).

(2) 25 hours of compulsory attendance to practical lectures (2h/week).

(3) 7,5 hours to take exams (partial and final exams).

(4) 85 hours of autonomous study and carrying out of homework and practices(5-6h/week).

(5) 7,5 hours of evaluation of homework and practices by means of tests.

We recommend studying the theory, to carry out the practices and to solve the exercises day by day, as it is required due to the assessment with weekly tests. Also, it is very important to go to tutorships to solve doubts.

The Virtual Campus of the USC will be used as a support tool in the learning process in the following ways: repository for slides and exercises, delivery and assessment of mandatory tasks and virtual tutorships (email and forums).


The software JFLAP will be used to carry out part of the practices bulletins. This software enables the design of automata and grammars, or apply the pumping lemma, among other features.

The predominant language of instruction in the subject will be Galician.