Sumários
11-02-2019 (Aula1)
- Apresentação da unidade curricular, condições de obtenção de frequência e modelo de avaliação.
- Noção de palavra e de linguagem sobre um alfabeto finito \(\Sigma\).
- A concatenação de palavras e suas propriedades.
13-02-2019 (Aula 2)
- Noção de prefixo, sufixo, infixo e reverso de uma palavra.
- Definição de tamanho de uma palavra.
- Operações sobre linguagens: reunião, concatenação e fecho de Kleene.
- Propriedades destas operações.
18-02-2019 (Aula 3)
- Expressões regulares.
- Semântica das expressões regulares.
- Autómatos finitos determinísticos (DFA).
- A linguagem definida por um DFA.
20-02-2019 (Aula 4)
- Autómato complementar de um autómato determinístico completo.
- Não determinismo.
- Autómatos Finitos Não-determinísticos NFA.
- A linguagem definida por um NFA.
- Transformação de um NFA num DFA.
25-02-2019 (Aula 5)
- O autómato produto. União e intersecção de linguagens regulares representadas por autómatos finitos.
- Autómatos Finitos Não-determinísticos com transições por \(\varepsilon\) (\(\varepsilon\)-NFA).
- Noção de fecho por \(\varepsilon\) de um estado.
- Conversão de \(\varepsilon\)-NFA em DFA.
- O \(\varepsilon\)-NFA concatenação de dois NFA e o \(\varepsilon\)-NFA que representa o fecho de Kleene de um NFA.
27-02-2019 (Aula 6)
- Obtenção de uma expressão representando a linguagem aceite por um autómato via resolução de um sistema de equações.
- Noção de quociente de uma linguagem por um símbolo.
- Derivadas (totais) de uma expressão regular por um símbolo.
- Algoritmo de Brzozowski para obtenção de um DFA reconhecendo a linguagem dada por uma expressão regular (autómato das derivadas)
04-03-2019 (Aula 7)
- Algoritmo de Glushkov para obter um NFA pequeno a reconhecendo a linguagem dada por uma expressão regular (autímato das posições).
06-03-2019 (Aula 8)
- Teorema de Myhill-Nerode
11-03-2019 (Aula 9)
- Algoritmo de minimização de Moore
13-03-2019 (Aulas 10)
- Existência de linguagens não regulares
- O Lema da Repetição para linguagens regulares
18-03-2019 (Aula 11)
- A surpreendente expressividade do não determinísmo. Os exemplos de $\frac12L$ e $rot(L)$.
20-03-2019 (Aula 12)
- Autómatos de pilha (PDA), determinísticos e não determinísticos.
- Equivalência do modelo de reconhecimento por estados de aceitação e por pilha vazia.
25-03-2019 (Aula 13)
- Gramáticas Independentes de Contexto (CFG)
- Noção de derivação de uma CFG
- Propriedades das CFL
- CFG lineares
27-03-2019 (Aula 14)
- Árvores de derivação.
- Noção de gramática ambígua e de linguagem ambígua.
- Desambiguamento de gramáticas
8-04-2019 (Aula 15)
- Forma normal de Chomsky para CFGs
- O algoritmo de parsing de Cocke-Younger-Kasimi (CYK)
10-04-2019 (Aula 16)
- Lema da Repetição para linguagens independentes do contexto
24-04-2019 (Aula 17)
- Operações fechadas para a classe das linguagens independentes do contexto.
- Algoritmos de detecção de linguagens independentes do contexto vazias ou finitas.
29-04-2019 (Aula 18)
- Equivalência entre a classe das linguagens definidas por autómatos de pilha (PDA) e por gramáticas independentes do contexto (CFG).
13-05-2019 (Aula 19)
- Máquinas de Turing.
- Existência de linguagens que não são decidíveis por Máquinas de Turing
15-05-2019 (Aula 20)
- Exemplos de Máquinas de Turing
20-05-2019 (Aula 21)
- Máquinas de Turing com mais do que uma fita
- Maquinas de Turing não determinísticas
- Equivalência da expressividade dos diversos modelos de Maquinas de Turing
22-05-2019 (Aula 22)
- Uma linguagem não decidível (o Halting Problem)
- Uma linguagem não reconhecível
- O teorema de Rice
29-05-2019 (Aula 23)
- Máquinas de Turing de comprimento mínimo e suas consequências
- Breve referência à complexidade de Kolmogorov
Última modificação: 18/04/2024