Course: 2024/2025

Automata and formal languages theory

(18266)

Requirements (Subjects that are assumed to be known)

Programming (Course 1º 1 semester)
Programming Techniques(Course 1º 2 semester)

Skills and learning outcomes

CB1. Students have demonstrated possession and understanding of knowledge in an area of study that builds on the foundation of general secondary education, and is usually at a level that, while relying on advanced textbooks, also includes some aspects that involve knowledge from the cutting edge of their field of study.
CB2. Students are able to apply their knowledge to their work or vocation in a professional manner and possess the competences usually demonstrated through the development and defence of arguments and problem solving within their field of study.
CB3. Students have the ability to gather and interpret relevant data (usually within their field of study) in order to make judgements which include reflection on relevant social, scientific or ethical issues.
CB4. Students should be able to communicate information, ideas, problems and solutions to both specialist and non-specialist audiences.
CB5. Students will have developed the learning skills necessary to undertake further study with a high degree of autonomy.
CG1. Students are able to demonstrate knowledge and understanding of concepts in mathematics, statistics and computation and to apply them to solve problems in science and engineering with an ability for analysis and synthesis.
CG3. Students can solve computationally with the help of the most advanced computing tools mathematical models coming from applications in science, engineering, economy and other social sciences.
CG4. Students are able to show that they can analyze and interpret, with help of computer science, the solutions obtained from problems associated to real world mathematical models, discriminating the most relevant behaviours for each application.
CG6. Students can search and use bibliographic resources, in physical or digital support, as they are needed to state and solve mathematically and computationally applied problems arising in new or unknown environments or with insufficient information.
CE14. Students have shown that they know the theory of grammars, languages and automatas and they can apply it to programming languages and domain specific languages analyzers as well as that they understand the translation process for high-level languages and most common optimizations.
CE21. Students have shown that they understand the influence and usefulness of the mathematical foundations used in functional programming languages and the impact of the practical applications of those languages.
RA3. Students must have the capacity to gather and interpret data and information on which they base their conclusions, including where relevant and necessary, reflections on matters of a social, scientific, and ethical nature in their field of study.
RA5. Students must know how to communication with all types of audiences (specialized or not) their knowledge, methodology, ideas, problems and solutions in the area of their field of study in a clear and precise way.
RA6. Students must be capable of identifying their own education and training needs in their field of study and the work or professional environment and organize their own learning with a high degree of autonomy in all types of contexts (structured or not).

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.
5.1. Definition if Turing Machine.
5.2. Variations of Turing Machine.
5.3. Universal Turing Machine.
8. Compilers
8.1. Syntactic Analysis
8.2. Code generation

Learning activities and methodology

LEARNING ACTIVITIES AND METHDOLOGY
THEORETICAL-PRACTICAL CLASSES. [44 hours with 100% classroom instruction, 1.67 ECTS]
Knowledge and concepts students must acquire. Student receive course notes and
will have basic reference texts to facilitate following the classes and carrying
out follow up work. Students partake in exercises to resolve practical problems
and participate in workshops and evaluation tests, all geared towards
acquiring the necessary capabilities.
TUTORING SESSIONS. [4 hours of tutoring with 100% on-site attendance, 0.15 ECTS]
Individualized attendance (individual tutoring) or in-group (group tutoring)
for students with a teacher.
STUDENT INDIVIDUAL WORK OR GROUP WORK [98 hours with 0 % on-site, 3.72 ECTS]
WORKSHOPS AND LABORATORY SESSIONS [8 hours with 100% on site, 0.3 ECTS]
FINAL EXAM. [4 hours with 100% on site, 0.15 ECTS]
Global assessment of knowledge, skills and capacities acquired throughout the
course.
METHODOLOGIES
THEORY CLASS. Classroom presentations by the teacher with IT and audiovisual
support in which the subject's main concepts are developed, while providing
material and bibliography to complement student learning.
PRACTICAL CLASS. Resolution of practical cases and problem, posed by the
teacher, and carried out individually or in a group.
TUTORING SESSIONS. Individualized attendance (individual tutoring sessions) or
in-group (group tutoring sessions) for students with a teacher as tutor.
LABORATORY PRACTICAL SESSIONS. Applied/experimental learning/teaching in
workshops and laboratories under the tutor's supervision.

Assessment System

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

Calendar of Continuous assessment

Extraordinary call: regulations

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. 2006. Jones & Bartlett Publishers, Sudbury, MA. ISBN 0763738344.

Additional Bibliography

- Brookshear, J. Glenn.. Teoría de la computación : lenguajes formales, autómatas y complejidad.. Addison Wesley Iberoamericana. 1993. ISBN: 9684443846.
- Jeffrey Shallit.. A Second Course in Formal Languages and Automata Theory.. Cambridge University Press, September 30 2008..
- Michael Sipser.. Introduction to the Theory of Computation (2nd Edition) 2006. Thomson Course Technology..
- Peter Linz. An Introduction to Formal Languages and Automata. Third Edition. Jones and Bartlett Publishers. ISBN: 0763714224..
- R. Penrose. La Nueva Mente del Emperador. Mondadori, 1991..

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