Sumários
12-02-2018 (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\).
- Operações sobre linguagens: reunião, concatenação e fecho de Kleene.
14-02-2018 (Aula 2)
- A Álgebra de Kleene da expressões regulares.
- Semântica das expressões regulares.
- Propriedades do fecho de Kleene.
19-02-2018 (Aula 3)
- Autómatos finitos determinísticos (DFA).
- A linguagem definida por um DFA.
- Autómato complementar de um autómato determinístico completo.
22-02-2018 (Aula 4)
- Não determinismo.
- Autómatos Finitos Não-determinísticos NFA.
- A linguagem definida por um NFA.
- Transformação de um NFA num DFA.
- O autómato produto. União e intersecção de linguagens regulares representadas por autómatos finitos.
26-02-2018 (Aula 5)
- 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.
28-02-2018 (Aula 6)
- Obtenção de uma expressão representando a linguagem aceite por um autómato pelo algoritmo de eliminação de estados.
- 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.
05-03-2018 (Aula 7)
- Algoritmo de Brzozowski para obtenção de um DFA reconhecendo a linguagem dada por uma expressão regular (autómato das derivadas)
07-03-2018 (Aula 8)
- Teorema de Myhill-Nerode
- Algoritmo de minimização de Moore
12-03-2018 (Aula 9)
- Existência de linguagens não regulares
- O Lema da Repetição para linguagens regulares
- Operações fechadas para linguagens regulares
14-03-2018 (Aulas 10)
- Autómatos de pilha (determinísticos e não-determinísticos)
- Linguagens independentes de Contexto
19-03-2018 (Aula 11)
- 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.
21-03-2018 (Aulas 12)
- Operações fechadas para a classe das linguagens independentes do contexto.
- Eliminação de símbolos inúteis e inatingíveis de uma gramática independente do contexto.
4-04-2018 (Aula 13)
- Forma normal de Chomsky para CFGs
- O algoritmo de parsing de Cocke-Younger-Kasimi (CYK)
09-04-2018 (Aula 14)
- Equivalência entre a classe das linguagens definidas por autómatos de pilha (PDA) e por gramáticas independentes do contexto (CFG).
11-04-2018 (Aula 15)
- Lema da Repetição para Linguagens independentes do Contexto
- $\{0^n1^n\mid n\in\mathbb{N}\}$ não é CFL
16-04-2018 (Aula 16)
- Noção de gramática ambígua e de linguagem intrinsecamente ambígua.
- Desambiguação de gramáticas.
18-04-2018 (Aula 17)
- Linguagens regulares e Linguagens Independentes do Contexto são fechadas para substituições assim como para homomorfismos e inversas de homomorfismos.
- As $CFL$ não são fechadas para intersecção ou complementação.
- As $CFL$ são fechadas para a intersecção com linguagens regulares.
23-04-2018 (Aula 18)
- Propriedades das Linguagens independentes do contexto determinísticas ($DCFL$)
30-04-2018 (Aula 19)
- Máquinas de Turing.
- Exemplo de uma Máquina de Turing.
2-05-2018 (Aula 20)
- 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
14-05-2018 (Aula 21)
- Linguagens reconhecíveis e decidíveis.
- A linguagem $A_{TM}$ é nõ decidível.
16-05-2018 (Aula 22)
- Técnicas de escrita de Máquinas de Turing
21-05-2018 (Aula 23)
- Técnicas de escrita de Máquinas de Turing
23-05-2018 (Aula 24)
- Máquinas de Turing de comprimento mínimo e suas consequências
- Breve referência à complexidade de Kolmogorov
Última modificação: 19/02/2025