Rogério Reis


Err and err and err again, but less and less and less.


Sumários

15FEV11
Apresentação do programa do curso e seus objectivos.
16FEV11
Rudimentos de Teoria de Conjuntos. Noção de linguagem e de palavra sobre um alfabeto. Concatenação, disjunção e fecho de Kleene de uma linguagem.
22FEV11
Expressões Regulares (RE). Linguagem definida por uma expressão regular. Propriedades das Expressões Regulares. A classe das Linguagens Regulares (RL) definida à custa das Expressões Regulares.
23FEV11
Noção de autómato finito determinístico (DFA). Noção de linguagem aceite por um DFA.
01MAR11
O complementar de um autómato determinístico completo. O autómato produto de dois DFAs.
02MAR11
Noção de autómato finito não determinístico (NFA) e de linguagem definida por este modelo. Transformação de um NFA num DFA equivalente.
09MAR11
Noção de autómato não determinístico com transições por epsilon (NFAe) e noção de linguagem definida por este modelo. Transformação de um NFAe num NFA.
15MAR11
Conversão de uma expressão regular num autómato finito. O autómato de Thompson. Conversão de um autómato finito numa expressão regular equivalente. O algoritmo de eliminação de estados de Brzozowski.
16MAR11
Noção de quociente esquerdo de uma linguagem por um símbolo e de derivada de uma expressão regular. O autómato de Brzozowski.
22MAR11
Noção de autómato determinístico mínimo. Existência e unicidade de tal autómato. O algoritmo de minimização de Moore.
23MAR11
O algoritmo de minimização de Brzozowski
29MAR11
Operações fechadas nas Linguagens Regulares. O Lema da Repetição (Pumping Lemma). Procedimentos de decisão decidíveis para as Linguagens Regulares.
30MAR11
Noção de gramática independente do contexto e de linguagem por ela aceite. Noção de derivação de uma palavra e de árvore de derivação de uma palavra.
05ABR11
Realização do teste intercalar
06ABR11
Demonstração da correcção de uma gramática. Eliminação de símbolos inacessíveis assim como de símbolos inúteis de uma gramática.
12ABR11
Forma Normal de Chomsky para Gramáticas Independentes do Contexto. O algoritmo CYK de reconhecimento de uma palavra por uma gramática.
13ABR11
Autómatos de pilha. Linguagem correspondente ao reconhecimento por pilha vazia e por estados finais.
26ABR11
Equivalência entre os modelos de avaliação de autómatos de pilha. Exemplos de autómatos de pilha para as linguagens independentes de contexto para as quais foi encontrada uma CFG.
27ABR11
Lema da repetição (Pumping Lemma) para linguagens independentes de contexto.
10MAI11
Lema de Ogden. Propriedades das linguagens independentes do contexto. Problemas decidíveis para linguagens independentes do contexto.
11MAI11
Exemplos de desambiaguação de gramáticas.
17MAI11
Noção de máquina de Turing. Noção de linguagem recursivamente enumerável e de linguagem recursiva.
18MAI11
Discussão da escrita de uma máquina de Turing.
24MAI11
Máquinas de Turing como avaliadoras de funções.
25MAI11
Equivalência dos diversos modelos de Máquinas de Turing. Construção de uma linguagem não recursivamente enumerável.
31MAI11
Problemas indecidíveis. A máquina universal de Turing e a sua linguagem. O problema da paragem.
01JUN11
Palavras aleatórios, palavras incomputáveis. O número Omega de Chaitin.