Programming (Course: 1 - Semester: 1) Algorithms and Data Structures (Course: 1 - Semester: 2)

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

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.