Automata

Code:

M3025

Acronym:

M3025

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2023/2024 - 2S

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:B	0	Official Study Plan	3	-	3	24	81
L:CC	0	study plan from 2021/22	2	-	3	24	81
			3
L:F	1	Official Study Plan	3	-	3	24	81
L:G	0	study plan from 2017/18	2	-	3	24	81
			3
L:M	8	Official Study Plan	3	-	3	24	81
L:MA	0	Official Study Plan	3	-	3	24	81
L:Q	0	study plan from 2016/17	3	-	3	24	81

Teaching language

Portuguese
Obs.: Suitable for English-speaking students

Objectives

This course intends to be an introduction to the theory of automata and of formal languages. We will focus our attention on finite automata and the languages recognized by them, namely the regular languages. We will see the equivalence (in terms of recognizable languages) between various models of  finite automata and the advantages of using each model.
Depending on the time available, we intend to make also a brief reference to more general mathematical models (pushdown automata and Turing machines) and to the languages recognized by them, mentioning the hierarchy of Chomsky for languages.

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

Course content:

1. Deterministic and complete finite automata.

2. Incomplete finite automata:

• Finite languages and count-based languages.

• The languages uA*, A*u and A*uA*.

• Boolean operations between languages.

• The Pumping Lemma.

3. Accessible automata (accessible part of a deterministic and complete finite automaton).

4. Non-deterministic (finite) automata:

• Equivalence between deterministic and complete finite automata and non-deterministic automata.

• Non-deterministic automata and recognizable languages.

5. Trimmed automata:

• Equivalence with the other models.

• Trimmed automata and recognizable languages.

6. ε-automata:

• Equivalence with the other models.

• ε-automata and recognizable languages.

7. Regular languages:

• Kleene's theorem: equivalence between regular languages and languages recognizable by finite automata.

8. Minimal automata (existence, uniqueness and construction).

We may also cover the following topics if time allows:

1. Minimal automata and monoids.

2. Brief reference to more general mathematical models:

• Pushdown automata and their languages.

• Turing machines.

• Chomsky hierarchy for languages.

 

Mandatory literature

Mark V. Lawson; Finite automata. ISBN: 1-58488-255-7

Complementary Bibliography

John M. Howie; Automata and languages. ISBN: 0-19-853424-8
Peter Linz; An introduction to formal languages and automata. ISBN: 978-1-4496-1552-9
Jean-Éric Pin; Mathematical Foundations of Automata Theory, 2020 (https://www.irif.fr/~jep//PDF/MPRI/MPRI.pdf)

Teaching methods and learning activities

During the (theoretical-practical) lessons, the course material will be explained using examples. Some exercises will be solved. Students will be given lecture notes (in addition to the bibliography) and some exercises to solve at home.

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	57,00
Frequência das aulas	24,00
Total:	81,00

Eligibility for exams

Not applicable

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.