Objetivos e enquadramento
Introdução ao estudo das linguagens formais. Pretende-se que o aluno seja capaz de especificar linguagens formais usando formas de descrição alternativas e determinar a sua classificação na hierarquia de poder computacional.
Resultados de aprendizagem e competências
Ao completar a unidade curricular, espera-se que os estudantes sejam capazes de:
Programa e conteúdos
Introdução ao estudo das linguagens formais. Pretende-se que o aluno seja capaz de especificar linguagens formais usando formas de descrição alternativas e determinar a sua classificação na hierarquia de poder computacional.
Resultados de aprendizagem e competências
Ao completar a unidade curricular, espera-se que os estudantes sejam capazes de:
- Especificar linguagens formais simples usando formas de descrição alternativas e de determinar a sua classificação na hierarquia de poder computacional.
- Identificar problemas tratáveis com autómatos finitos
- Comparar os autómatos finitos determinísticos, não-determinísticos e as expressões regulares no reconhecimento das linguagens regulares;
- Usar as propriedades das linguagens regulares;
- Identificar problemas que se podem tratar com gramáticas independentes de contexto e descrevê-los usando esses formalismos;
- Comparar gramáticas independentes de contexto e os autómatos de pilha no reconhecimento das LICS;
- Exprimir problemas usando máquina de Turing;
- Relacionar os modelos de computação estudados com as suas aplicações na teoria da computabilidade e da complexidade.
Programa e conteúdos
- Noção de linguagem formal.
- Linguagens regulares e expressões regulares
- Autómatos finitos determinísticos e não determinísticos.
- Propriedades das linguagens regulares;
- Minimização de autómatos finitos determinísticos. Lema da repetição para linguagens regulares.
- Linguagens e gramáticas independentes de contexto.
- Autómatos de pilha;
- Propriedades das linguagens independentes de contexto (LIC). Lema da repetição para LICs.
- Introdução às Máquinas de Turing e noção de computabilidade.