Sumários das aulas teóricas de LFA
2007/2008 - 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.
(acetatos: 11-13,
exercícios)
Autómatos finitos não deterministas: motivação e definição;
computação, palavras aceites e linguagem reconhecida.
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.
(acetatos: 14-17,
exemplos da aula)
Estados equivalentes. Minimização de autómatos finitos deterministas.
(exemplo da aula)
Construção de autómatos finitos por composição de autómatos.
Linguagens regulares: equivalência entre as linguagens representadas
por expressões regulares e as reconhecidas por autómatos finitos
deterministas. O Pumping Lemma para linguagens regulares.
(acetatos: 18-22)
Gramáticas: símbolos terminais, não terminais e
produções; derivação. Gramáticas independentes do contexto: definição;
derivação directa e em n passos; recursividade, recursividade
directa e indirecta; palavras deriváveis; linguagem gerada; 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.
(acetatos: 23-32)
Resolução da 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 deterministas (e as representadas por expressões
regulares).
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: 33-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; funcionamento de um
algoritmo de análise sintáctica ascendente em profundidade.
(acetatos: 40-45, exemplos da aula)
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); símbolos úteis (produtivos e
acessíveis); eliminação dos símbolos inúteis; forma normal de Chomsky.
(acetatos: 46-51)
Gramáticas independentes do contexto: forma normal de Greibach;
eliminação da recursividade directa à esquerda.
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 e SEGUINTES. Factorização à esquerda de uma
gramática.
(acetatos: 52-57)
Gramáticas LL(1): símbolos directores de uma produção; cálculo dos
PRIMEIROS e dos SEGUINTES; 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.
(acetatos: 57-62)
Gramáticas LR(0): 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); 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).
(acetatos: 63-69)
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: 70-78)
Exercício. (EEA)
Computabilidade: problemas de decisão; decidibilidade; tese de
Church-Turing; o problema da terminação; computabilidade; redução de
problemas; teorema de Rice; alguns problemas indecidíveis.
(acetatos: 79-88)
Realização da 2ª frequência.