Course: 2022/2023

Automata theory and compilers

(16491)

Requirements (Subjects that are assumed to be known)

Programming
Algorithms and Data Structures

Skills and learning outcomes

Description of contents: programme

1.Introduction to the theory of automata and formal languages.
1.1. Why study Automata Theory. History and Origins
1.2. Relationship with others Areas of Knowledge
1.3. Machines, Languages and Algorithms.
2.- Automata Theory
2.1 Introduction and Definitions.
2.2 Mathematical model of an automaton
2.3 Automata and algorithms.
2.4 Discrete, continuous, and hybrid automata. Classes of automata.
3.Finite Automata
3.1 Definition and Representation of Deterministic Finite Automata (DFA)
3.2. DFA as Recognition Device
3.3. Equivalence and Minimization of DFA
3.4. Theorems of DFA
3.5. Definition and Representation of Nondeterministic Finite Automata (NDFA)
3.6. The Language of a NDFA
3.7. Equivalence of DFA and NDFA
4.Languages and Formal Grammars.
4.1. Operations with Words. Operations with Languages. Derivations.
4.2 Concept of Grammar. Formal Grammar.
4.3. Chomsky Hierarchy and Equivalent Grammar
4.4 Context-Free Grammar
4.5. Language of a Context-Free Grammar. Parse Tree
4.6. Well-Formed Grammar
4.7. Chomsky Normal Form. Greibach Normal Form
5.Regular Languages.
5.1. Definition of Regular Languages
5.2. DFA for a Regular Grammar
5.3. Equivalence of Regular Expressions
5.4. Kleene's Theorem
5.5. Characteristic equations
5.6. Synthesis Problem: Recursive Algorithm
5.7. Derivatives of Regular Expressions
6.Pushdown Automata.
6.1. Definition of Pushdown Automata (PDA).
6.2. Transitions, Movement and Instantaneous Description in PDA.
6.3. Acceptance by Empty Stack. Acceptance by Final State.
6.4. Language Accepted by a PDA.
Equivalence of PDA by Empty Stack and PDA by Final State.
6.5. From Context-Free Grammar to Push-Down Automata.
6.6. From Pushdown Automata to Context-Free Grammar.
7.Turing Machine.
7.1. Definition if Turing Machine.
7.2. Variations of Turing Machine.
7.3. Universal Turing Machine.
8.Computational Complexity
8.1.Complexity Theory
8.2.Complexity of algorithms
8.3.P versus NP problems
8.4 Defining complexity classes
8.5 Time complexity
8.6 Hierarchy theorems
8.7 Non-computational problems
8.9 Limits of Computability

Learning activities and methodology

THEORETICAL-PRACTICAL CLASSES (theoretical content): 3.5 ECTS.
The knowledge to be acquired by the students will be presented. They will receive the class notes and will have basic reference texts to facilitate the follow-up of the classes and the development of the subsequent work. Exercises will be solved by the student that will serve as self-evaluation and to acquire the necessary skills. Classes of problems, in which the problems proposed to the students will be developed and discussed.
WORKSHOPS AND/OR LABORATORY PRACTICES. 1.5 ECTS.
Developed with or without the presence of the teacher, they aim to complete and integrate the development of all the specific and transversal competences, in the resolution of two practical cases where the approach to the problem, the choice of the resolution method, the results obtained and their interpretation are well documented.
FINAL EXAM. 0,5 ECTS
The knowledge, skills and abilities acquired throughout the course will be globally assessed.
TUTORIALS. 0,5 ECTS
Individualized assistance (individual tutorials) or in group (collective tutorials) to the students by the professor.

Assessment System

- % end-of-term-examination 50
- % of continuous assessment (assigments, laboratory, practicals...) 50

Basic Bibliography

- Enrique Alfonseca Cubero, Manuel Alfonseca Cubero, Roberto Moriyón Salomón.. Teoría de autómatas y lenguajes formales.. McGraw-Hill. 2007
- John E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman.. Introduction to Automata Theory, Languages, and Computation (Third Edition). Pearson Education, Pearson Addison Wesley.
- Manuel Alfonseca, Justo Sancho, Miguel Martínez Orga.. Teoría de lenguajes, gramáticas y autómatas.. Publicaciones R.A.E.C. ISBN: 8460560929. . 1997.
- Pedro Isasi, Paloma Martínez y Daniel Borrajo.. Lenguajes, Gramáticas y Autómatas. Un enfoque práctico.. Addison-Wesley. 1997
- Susan H. Rodger and Thomas W. Finley.. JFLAP: An Interactive Formal Languages and Automata Package. . web. 2006

The course syllabus may change due academic events or other reasons.