Autómatos

Código:

M3025

Sigla:

M3025

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

Ocorrência: 2022/2023 - 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:M	15	Plano de Estudos Oficial	3	-	3	28	81
L:MA	0	Plano de Estudos Oficial	3	-	3	28	81

Língua de trabalho

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

Objetivos

Adquirir uma visão geral da teoria de autómatos e conhecimentos de uma teoria clássica de linguagens formais: a hierarquia de Chomsky de linguagens. Para o efeito serão usadas gramáticas (as da hierarquia de Chomsky) e máquinas, que vão dos autómatos finitos, às máquinas de Turing.

No primeiro nível da hierarquia (linguagens racionais e autómatos finitos) deverá ser adquirida alguma familiaridade com o uso de ferramentas computacionais.

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

I Autómatos finitos

1. Autómatos finitos: propriedades de fecho e Teorema de Kleene

- Linguagens racionais

- Autómatos finitos

- Equivalência de diversos modelos de autómato

- Propriedades de fecho

- O Teorema de Kleene

2. Autómatos mínimos e decidibilidade

- Construção e unicidade do autómato mínimo

- O pumping lemma

- Propriedades decidíveis

- Classificação das linguagens racionais

II Generalizações

3. Memória ilimitada: os autómatos de pilha

- Autómatos de pilha

- Gramáticas independentes de contexto

- Propriedades de fecho

- Decidibilidade e indecidibilidade

4. Máquinas de Turing e computabilidade

- Máquina de Turing

- Equivalência de diversos modelos

- A máquina de Turing universal

5. A hierarquia de Chomsky revisitada.

--
A segunda parte, Generalizações, será abordada com pouco detalhe e diversas provas serão omitidas.

Bibliografia Obrigatória

John M. Howie; Automata and languages. ISBN: 0-19-853424-8

Bibliografia Complementar

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

1. Aulas teórico-práticas: exposição da matéria e apresentação de exemplos pelo docente; resolução de exercícios pelos estudantes com apoio do docente.
2. Horário regular de atendimento para apoio e esclarecimento de dúvidas.
3. Além da bibliografia indicada, poderão ser disponibilizadas outras notas.

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 (%)
Teste	100,00
Total:	100,00

Componentes de Ocupação

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

Obtenção de frequência

A avaliação é feita por doi s testes.Não existem quaisquer requisitos. Todos os estudantes inscritos são admitidos ao teste e ao exame final.

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

Todos os estudantes inscritos são admitidos aos testes. Os testes  contam cada um com 50% da nota final.
No exame de recurso os estudantes podem obter para manter uma nota de um dos teste.

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.