Autómatos e Linguagens Formais | Informações
Informação geral
Código: 10859
Área científica predominante: Ciências da Computação
Regime: Semestral
ECTS: 5
Tipo de ensino: Presencial
Língua de instrução: Português
Carga Horária
Trabalho autónomo: 80 horas
Aulas:
30 horas - Teóricas
30 horas - Teórico-práticas
Objetivos de ensino
A UC é lecionada às Licenciaturas em Matemática no semestre 6 (opcional) e em Ciências da Computação no semestre 4.
Neste curso é complementada com a formação em Computabilidade e Complexidade no semestre 6.
Pretende desenvolver capacidades de análise, cálculo e compreensão sobre os fundamentos de linguagens formais, autómatos e gramáticas.
Resultados de aprendizagem
- Conhecer os conceitos básicos relacionados com linguagens formais, autómatos e gramáticas;
- Identificar linguagens regulares;
- Relacionar as noções de autómatos finitos, linguagens reconhecíveis e linguagens regulares;
- Verificar se uma palavra é aceite por um autómato de pilha;
- Determinar a linguagem gerada por uma gramática independente de contexto e o autómato de pilha que a reconhece;
- Reconhecer os autómatos como modelos abstratos de computação.
Programa sucinto
- Linguagens formais.
- Expressões regulares e linguagens regulares.
- Autómatos finitos deterministas e autómatos finitos não deterministas.
- Equivalência entre estes dois tipos de autómatos.
- Teorema de Kleene.
- Minimização de autómatos.
- Lema da bombagem.
- Gramáticas independentes de contexto.
- Autómatos de pilha.
- Correspondência entre gramáticas independentes de contexto e autómatos de pilha.
Bibliografia essencial
- J. Hopcroftt, R. Motwani, J. Ullman . Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
- J. Martin. Introduction to Languages and the Theory of Computation. McGraw-Hill, 1996.
- T. Sudkamp. Languages and Machines. Addison-Wesley, 1997.
Métodos de ensino
As aulas são de caráter teórico-prático com exposição das matérias, incluindo exemplos de aplicação e incentivando a participação e interação dos estudantes, seguida da resolução de exercícios previamente disponibilizados aos alunos através da plataforma de e-learning.
Métodos de avaliação
O sistema de avaliação é definido anualmente nos termos estabelecidos no Regulamento Académico.
A avaliação pode ser contínua ou periódica, combinando dois ou mais instrumentos de avaliação.
A nota final é calculada a partir das classificações obtidas em cada elemento de avaliação, através de fórmula indicada no Dossiê da Unidade Curricular.
