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:
  • 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.