Sumários das aulas práticas de LFA
2007/2008 - 1º semestre.
[Aulas: 1 2
3 4
5 6
7 8
9 10
11 12
13 14]
Exemplos de alfabetos e de palavras e linguagens sobre esses
alfabetos. Definição recursiva de conjuntos.
EEA
Subpalavras, prefixos e sufixos. Leitura e criação de expressões
regulares.
EEA
Definição de autómatos finitos deterministas e não
deterministas. Construção do autómato finito determinista equivalente
a um autómato finito não determinista.
EEA
Minimização de autómatos finitos deterministas. Aplicação do
Pumping Lemma para linguagens regulares.
EEA
Leitura, criação e desambiguação de gramáticas independentes do
contexto.
EEA
Revisões.
Construção de autómatos de pilha.
EEA
Análise sintáctica ascendente em profundidade: transferência e
redução; efeito da recursividade à direita e à esquerda.
Construção de gramáticas independentes do contexto (essencialmente)
não contraíveis. Eliminação de produções unitárias (da forma
A->B, onde B é um símbolo não terminal).
Eliminação de símbolos inúteis de gramáticas independentes do
contexto. Construção da forma normal de Chomsky.
EEA
Construção da forma normal de Greibach. Gramáticas LL(1): primeiros
passos.
EEA
Verificação das condições LL(1) em gramáticas independentes do
contexto.
EEA
Construção do autómato dos itens LR(0) válidos e verificação das
condições LR(0). Construção da tabela de análise sintáctica LR(0).
EEA
Demonstração da indecidibilidade de problemas através da redução entre
problemas.
EEA
Correcção parcial da 2ª frequência.