Código: 21078
Departamento: DCET
ECTS: 6
Área científica: Engenharia Informática
Total de horas trabalho: 156
Total de horas de contacto: 26

A relação entre as linguagens formais e a computação é o tema desta unidade curricular. São abordados os vários formalismos de representação de linguagens, até ao conceito que deu origem ao computador actual: a máquina de Turing. As noções de decidibilidade, tratabilidade e complexidade computacional estão intimamente relacionadas com este conceito.

1. Linguagens regulares
2. Linguagens independentes do contexto
3. Máquinas de Turing
4. Decidibilidade e tratabilidade

Ao concluir esta unidade curricular o aluno deverá estar capaz de:
Compreender e aplicar os vários tipos de linguagens formais.
Estabelecer relações entre algoritmos/problemas e a sua representação formal em termos de máquina de Turing.

Autómatos.
Expressões e linguagens regulares.
Gramáticas e linguagens independentes do contexto.
Máquinas de Turing.
Decidibilidade e Tratabilidade.

Hopcroft & Ullman. Introduction to Automata and Language Theory. Addison-Wesley.
Valença & Barros. Fundamentos da Computação, Vol. I & II. Universidade Aberta.

E-learning.

O regime de avaliação preferencial é o de avaliação contínua, constituída pela realização de 2/3 e-folios (trabalhos escritos em formato digital), ao longo do semestre letivo, e de um momento final de avaliação presencial (p-fólio), a ter lugar no final do semestre, com peso de, respetivamente, 40% e 60% na classificação final. Os estudantes podem, no entanto, em devido tempo, optar um único momento presencial de avaliação, realizando, então uma prova de Avaliação Final (exame) com o peso de 100%.