• Linguagens Formais e Autómatos do 5º semestre lectivo da licenciatura em Engenharia Informática

Responsável: José Júlio Alves Alferes 

Esta disciplina tem por objectivo estudar os conceitos de linguagens formais, gramáticas livres de contexto e de autómatos, com aplicação prática à análise sintáctica de programas.

1. Introdução e motivação para a disciplina
1. Apresentação da disciplina
2. Pré-requisitos matemáticos
1. Teoria de conjuntos
2. Relações e funções
3. Relações de equivalência
4. Indução
3. Conceitos básicos de linguagens
1. "String" e linguagens
2. Especificação finita de linguagens
3. Expressões regulares
2. Gramáticas livres de contexto
1. Definição e geração de linguagens
2. Derivação e árvores de derivação
3. Gramáticas regulares
3. Introdução à análise sintática
1. Derivações esquerdas e direitas
2. Grafo correspondente a uma gramática
3. Ambiguidade nas gramáticas
4. Analisadores sintáticos "top-down"
1. Com pesquisa em largura
2. Com pesquisa em profundidade
5. Analisadores sintáticos "bottom-up"
1. Com pesquisa em largura
2. Com pesquisa em profundidade
4. Formas normais de gramáticas
1. Forma Normal de Chomsky
2. Forma Normal de Greibach
5. Autómatos finitos
1. Autómatos finitos deterministicos
2. Autómatos finitos não-deterministicos com transições-l
3. Remoção de não-determinismo
4. Minimização de autómatos
5. Relação entre autómatos finitos, gramáticas regulares e expressões regulares.
6. Linguagens não-regulares, e "pumping" lemma.
6. Autómatos de pilha
1. Definições básicas e construção de autómatos para linguagens livres de contexto
2. Autómatos de pilha e gramáticas livres de contexto
7. Análise sintática deterministica
1. Gramáticas LL(K)
2. Gramáticas LR(K)

• Referência de base:

• Teóricas: José Alferes
• Práticas: José Alferes

Duas frequências (sendo a nota final a média aritmética) ou exame final.