Autómatos

Código:

M3025

Sigla:

M3025

Áreas Científicas
Classificação	Área Científica
OFICIAL	Matemática

Ocorrência: 2023/2024 - 2S

Ativa?	Sim
Página Web:	https://moodle.up.pt/course/view.php?id=3590
Unidade Responsável:	Departamento de Matemática
Curso/CE Responsável:	Licenciatura em Matemática

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
L:B	0	Plano de Estudos Oficial	3	-	3	24	81
L:CC	0	Plano estudos a partir do ano letivo 2021/22	2	-	3	24	81
			3
L:F	1	Plano de Estudos Oficial	3	-	3	24	81
L:G	0	Plano estudos a partir do ano letivo 2017/18	2	-	3	24	81
			3
L:M	8	Plano de Estudos Oficial	3	-	3	24	81
L:MA	0	Plano de Estudos Oficial	3	-	3	24	81
L:Q	0	Plano estudos a partir do ano letivo 2016/17	3	-	3	24	81

Língua de trabalho

Português
Obs.: Suitable for English-speaking students

Objetivos

Este curso pretende ser uma introdução à teoria de autómatos e de linguagens formais. Iremos focar-nos nos autómatos finitos e nas linguagens reconhecíveis por estes, nomeadamente as linguagens regulares. Veremos a equivalência (em termos de linguagens reconhecíveis) entre vários modelos destes autómatos e as vantagens de utilizar uns e outros.
Consoante o tempo disponível pretende-se fazer também uma breve referência a modelos matemáticos mais gerais (autómatos de pilha e máquinas de Turing) e das linguagens reconhecíveis por estes modelos, mencionando a hierarquia de Chomsky para linguagens.

Resultados de aprendizagem e competências

No final da Unidade Curricular os estudantes deverão revelar alguma familiaridade com a Teoria de Autómatos e Linguagens Formais.

Modo de trabalho

Presencial

Programa

1. 
   

   Autómatos finitos determinísticos e completos.

   
   


2. 
   

   Autómatos finitos incompletos:

   
   




• 
  

  Linguagens finitas e linguagens baseadas em contagens.

  
  


• 
  

  As linguagens uA*, A*u e A*uA*.

  
  


• 
  

  Operações booleanas entre linguagens.

  
  


• 
  

  The Pumping Lemma.

  
  




3. 
   

   Autómatos acessíveis (parte acessível de um autómatos finito determinístico e completo).

   
   


4. 
   

   Autómatos (finitos) não determinísticos:

   
   




• 
  

  Equivalência entre autómatos finitos determinísticos e completos e autómatos não determinísticos.

  
  


• 
  

  Autómatos não determinísticos e linguagens reconhecíveis.

  
  




5. 
   

   Autómatos aparados:

   
   




• 
  

  Equivalência com os outros modelos.

  
  


• 
  

  Autómatos aparados e linguagens reconhecíveis.

  
  




6. 
   

   ε-autómatos:

   
   




• 
  

  Equivalência com os outros modelos.

  
  


• 
  

  ε-autómatos e linguagens reconhecíveis.

  
  




7. 
   

   Linguagens regulares:

   
   




• 
  

  Teorema de Kleene: equivalência entre linguagens regulares e linguagens reconhecíveis por autómatos finitos.

  
  




8. 
   

   Autómatos minimais (existência, unicidade e construção).

   
   

Poderemos ainda abordar os seguintes temas se o tempo o permitir:

1. 
   

   Autómatos minimais e monoides.

   
   


2. 
   

   Breve referência a modelos matemáticos mais gerais:

   
   




• 
  

  Autómatos de pilha e respetivas linguagens.

  
  


• 
  

  Máquinas de Turing.

  
  


• 
  

  Hierarquia de Chomsky para linguagens.

  
  

 

Bibliografia Obrigatória

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

Bibliografia Complementar

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)

Métodos de ensino e atividades de aprendizagem

Durante as aulas (teórico-práticas) será exposta a matéria do curso com recurso a exemplos. Serão resolvidos alguns exercícios. Será fornecido aos estudantes apontamentos das aulas (para além da bibliografia) e alguns exercícios para resolverem em casa.

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/

Tipo de avaliação

Avaliação por exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	100,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Estudo autónomo	57,00
Frequência das aulas	24,00
Total:	81,00

Obtenção de frequência

Não aplicável

Fórmula de cálculo da classificação final

Classificação do exame final. Durante o semestre poderá ser pedido aos estudantes para entregarem alguns exercícios resolvidos, que poderão ser usados depois para substituir parte do exame final da época normal.

Avaliação especial (TE, DA, ...)

Exames requeridos ao abrigo de estatutos especiais consistirão de uma prova escrita que poderá ser precedida de uma prova oral eliminatória para avaliar se o estudante está em condições mínimas de obter aprovação à disciplina na prova escrita.

Melhoria de classificação

Por exame.