Automata

Code:

M3025

Acronym:

M3025

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2021/2022 - 1S

Active?	Yes
Web Page:	https://moodle.up.pt/course/view.php?id=3590
Responsible unit:	Department of Mathematics
Course/CS Responsible:	Bachelor in Mathematics

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:M	19	Official Study Plan	2	-	3	28	81
			3

Teaching language

Portuguese
Obs.: Suitable for English-speaking students

Objectives

To acquire a general vision of automata theory and some knowledge on the classical theory of formal languages: the Chomsky hierarchy of languages. To this effect, grammars and machines will be used. The grammars are those of Chomsky's hierarchy. The machines go from the finite automata to the Turing machines.

At the first level of the hierarchy, (rational languages and finite automata), acquiring some familiarity with computational tools is also expected.

Learning outcomes and competences

At the end of the course, students should reveal some familiarity with Automata and Formal Language Theory.

Working method

Presencial

Program

I Finite automata

1. Finite automata: Closure properties and Kleene's Theorem

- Rational languages

- Finite automata

- Equivalence of various automata models

- Closure properties

- Kleene's Theorem

2. Minimal automata and decidability

- Construction and unicity of the minimal automata

- The Pumping Lemma

- Classification of rational languages

- Decidability properties

II Generalizations

3. Unlimited memory: push-down automata

- Push-down automata

- Context-free grammars

- Closure properties

- Decidability and undecidability

4. Turing Machines and computability

- Turing machines

- Equivalence of various models

- The universal Turing machine

5. Chomsky's hierarchy revisited.

--
The second part, Generalizations, is to be covered with little detail, and several proofs will be omitted.

Mandatory literature

Peter Linz; An introduction to formal languages and automata. ISBN: 978-1-4496-1552-9

Complementary Bibliography

John M. Howie; Automata and languages. ISBN: 0-19-853424-8
Jean-Éric Pin; Mathematical Foundations of Automata Theory, 2020 (https://www.irif.fr/~jep//PDF/MPRI/MPRI.pdf)

Teaching methods and learning activities

1. Lectures: presentation of the course material and of examples by the teacher; solution of exercises by the students with the advice of the teacher.
2. Regular office hours for student advice and clarification of doubts.
3. Besides the bibliography list, some other notes may be made available for the students.

Software

M.Delgado S. Linton e J. Morais, 'automata', a GAP package for finite state automata, Version 1.14, 2018, http://www.gap-system.org/Packages/automata.html
The GAP Group. GAP -- Groups, Algorithms, and Programming, Version 4.11.1, 2021. http://www.gap-system.org/

Evaluation Type

Evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	100,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Estudo autónomo	53,00
Frequência das aulas	28,00
Total:	81,00

Eligibility for exams

Course registration is the only requirement. All enrolled students are admitted to the final exam.

Calculation formula of final grade

Special assessment (TE, DA, ...)

The exams required under the special legal cases will be written but can be preceded by an oral exam to establish if the student should be admitted to the written exam.

Classification improvement

Exam.