Sumários das aulas teóricas de LFA
2008/2009 - 1º semestre.
[Aulas: 1 2
3 4
5 6
7 8
9 10
11 12
13 14
15]
Apresentação da disciplina. Marcação das avaliações.
Linguagem formal vs. linguagem natural. Noções básicas:
alfabeto; símbolo; palavra sobre um alfabeto; palavra vazia; conjunto
de todas as palavras sobre um alfabeto; linguagem (sobre um
alfabeto). Definições recursivas de conjuntos.
(acetatos: 1-2)
Princípio da indução matemática. Comprimento de uma palavra.
Concatenação de palavras; associatividade da concatenação de palavras.
Inversão e potências de palavras; subpalavra, prefixo e sufixo.
Caracterização de linguagens através de definições recursivas e de
operações sobre conjuntos. Concatenação de linguagens; potências de
uma linguagem; estrela de Kleene (fecho, iteração) de um conjunto.
Conjuntos regulares.
Expressões regulares: definição; associatividade e precedências dos
operadores; exemplos; linguagem representada; equivalência de
expressões regulares; propriedades.
(acetatos: 3-10)
Autómatos finitos deterministas: motivação e princípios; definição;
configuração de um AFD e computação; função de transição estendida;
palavras aceites e linguagem reconhecida; exemplos.
Autómatos finitos não deterministas: motivação e definição;
computação, palavras aceites e linguagem reconhecida.
(acetatos: 11-15)
Autómatos finitos não deterministas com transições lambda
(AFND): motivação e definição; computação, palavras aceites e
linguagem reconhecida. Construção do autómato finito determinista que
simula um autómato finito não determinista com transições
lambda.
Estados equivalentes. Minimização de autómatos finitos deterministas.
(acetatos: 16-20,
exemplos da aula)
Linguagens regulares: construção de autómatos finitos por composição
de autómatos; equivalência entre as linguagens representadas por
expressões regulares e as reconhecidas por autómatos finitos. O
Pumping Lemma para linguagens regulares. Linguagens não
regulares
Gramáticas: motivação; símbolos terminais e não terminais; reescrita;
derivação e passo de derivação. Gramáticas independentes do contexto:
definição; produções; derivação directa e em n passos;
recursividade, recursividade directa e indirecta; palavras deriváveis;
linguagem gerada.
(acetatos: 21-28)
Gramáticas independentes do contexto: linguagens independentes do
contexto; derivações esquerdas e direitas; existência de derivação
esquerda; árvores de derivação; gramáticas ambíguas e linguagens
inerentemente ambíguas. Ambiguidade nas expressões aritméticas.
Gramáticas e linguagens regulares: equivalência entre as linguagens
geradas por gramáticas regulares e as reconhecidas por autómatos
finitos (e as representadas por expressões regulares).
(acetatos: 29-33)
Autómatos de pilha: motivação, princípio de funcionamento e definição;
configuração e computação; aceitação pelo critério de estado de
aceitação e pilha vazia; linguagem reconhecida; determinismo;
autómatos de pilha atómicos e estendidos.
Linguagens independentes do contexto: equivalência entre as linguagens
reconhecidas por autómatos de pilha e as geradas por gramáticas
independentes do contexto. O Pumping Lemma para linguagens
independentes do contexto. A hierarquia de Chomsky.
(acetatos: 34-39)
Análise sintáctica: grafos (esquerdo, direito e completo) de uma
gramática independente do contexto; prefixo terminal; funcionamento da
análise sintáctica descendente e ascendente, em profundidade e em
largura; terminação nas análises sintácticas descendente e ascendente;
transferência (shift) e redução.
Gramáticas independentes do contexto: símbolo inicial recursivo;
eliminação da recursividade do símbolo inicial; gramáticas não
contraíveis e essencialmente não contraíveis; símbolos que geram
lambda; eliminação das produções-lambda; eliminação das produções
unitárias (da forma A -> B).
(acetatos: 40-49, exemplos da aula)
Gramáticas independentes do contexto: símbolos úteis (produtivos e
acessíveis); eliminação dos símbolos inúteis; forma normal de Chomsky;
forma normal de Greibach; eliminação da recursividade directa à
esquerda.
(acetatos: 50-53)
Gramáticas LL(k): motivação, análise sintáctica descendente
determinista e com símbolos de avanço. Gramáticas LL(1): definição e
consequências; PRIMEIROS, SEGUINTES e símbolos directores de uma
produção; cálculo dos PRIMEIROS e dos SEGUINTES. Factorização à
esquerda de uma gramática.
(acetatos: 54-61)
Gramáticas LL(1): analisadores sintácticos descendentes recursivos.
Gramáticas LR(k): motivação, análise sintáctica ascendente
determinista com símbolos de avanço. Gramáticas LR(0): contexto-LR(0)
e prefixo viável; item LR(0), item completo e item válido; fecho de um
conjunto de itens; autómato dos itens LR(0) válidos; definição de
gramática LR(0).
(acetatos: 61(1)-66)
Gramáticas LR(0): algoritmo de análise sintáctica LR(0); tabela de
análise sintáctica LR(0); autómato de pilha que reconhece a linguagem
gerada por uma gramática LR(0).
Análise sintáctica LR(1). Gramáticas LR(1): motivação; item LR(1);
item válido; fecho de um conjunto de itens; autómato dos itens LR(1)
válidos; condições LR(1); tabela de análise sintáctica LR(1); autómato
de pilha que reconhece a linguagem gerada por uma gramática LR(1);
autómato amalgamado; gramáticas LALR(1); verificação das condições
LR(0) a partir do autómato dos itens LR(1) válidos.
(acetatos: 67-78)
Exemplos de redução de problemas. A linguagem WHILE.
Computabilidade: problemas de decisão; decidibilidade; tese de
Church-Turing; o problema da terminação; computabilidade.
(acetatos: 79-85)
Computabilidade: redução de problemas; demonstração da
indecidibilidade através da redução de problemas; teorema de Rice;
alguns problemas indecidíveis. Exemplo de aplicação.
(acetatos: 85-88)
Aula de dúvidas.