Ficha

Versión en español

Course: 2022/2023

Automata and formal languages theory

(18266)

Bachelor in Applied Mathematics and Computing (Plan: 433 - Estudio: 362)

Coordinating teacher: SANCHIS DE MIGUEL, MARIA ARACELI

Department assigned to the subject: Computer Science and Engineering Department

Type: Compulsory

ECTS Credits: 6.0 ECTS

Course: 2º

Semester: 1º

Requirements (Subjects that are assumed to be known)

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

Skills and learning outcomes

Link to document

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

The evaluation will consist in continuous assessment SE2 and a final exam SE1.

The aim of continuous assessment is to help the students keep track of their learning 
progress, obtaining continous feedback about the competences acquired during the semester. 
This way,mid-term exams and practices are intended to be both learning and evaluation 
activities.

The aim of the final exam is to assess the extent to which the students have acquired the 
cognitive and procedural competences. 

The continuous assessment SE1 will sum up 50% of the final grade. The continuous assessment 
will consist of: 
  - Three mid-term exams (test questions, short questions and problems),and
  - Four practical assignments using JFLAP software tool
    (http://www.cs.duke.edu/csed/jflap/). 
 
  
  Each mid-term exam will sum up 12% of the final grade 
  and the practical assessments 14% of the final grade.


The final exam SE2 (50 % of grade) will consist in theoretical questions as well as practical 
exercises.

 
More than 4 points in the final exam will be required to sum continuous assessment.

SE1 - FINAL EXAM. [50 %]
Global assessment of knowledge, skills and capacities acquired throughout the
course.

SE2 - CONTINUOUS EVALUATION. [50 %]
Assesses papers, projects, class presentations, debates, exercises, internships
and workshops throughout the course.

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

Calendar of Continuous assessment

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.