Rogério Reis


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


Sumários

11-02-2020 (Aula 1)
  • 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.
18-02-2020 (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.
21-02-2020 (Aula 3)
  • Expressões regulares.
  • Semântica das expressões regulares.
  • Autómatos finitos determinísticos (DFA).
  • A linguagem definida por um DFA.
28-02-2020 (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.
  • O autómato da linguagem reversa ($L^R$) de uma linguagem regular.
3-03-2020 (Aula 5)
  • Simulação (transformação) de um NFA num DFA.
  • O autómato produto. União e intersecção de linguagens regulares representadas por autómatos finitos.
10-03-2020 (Aula 6)

  • 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.
17-03-2020 (Aula 7)
Stacks Image 195
  • 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)
20-03-2020 (Aula 8)
Stacks Image 204
  • A construção de Glushkov de um NFA que representa a linguagem dada por uma expressão regular.
  • O Teorema de Myhill-Nerode
24-03-2020 (Aula 9)
Stacks Image 215
  • Algoritmo de minimização de Moore
  • Algoritmo de minimização de Brzozowski
27-03-2020 (Aula 10)
Stacks Image 226
  • Existência de linguagens não regulares
  • O Lema da Repetição para linguagens regulares
31-03-2020 (Aula 11)
Stacks Image 237
  • Fecho da classe das linguagens regulares RL para: complementação, operações binárias booleanas e reversão de palavras.
  • A imagem de uma linguagem regular por uma substituição é também regular assim como a imagem inversa de por um homomorfismo.
  • Noção de quociente de duas linguagens e regularidade do quociente de uma linguagem regular por qual quer linguagem.
03-04-2020 (Aula 12)
Stacks Image 248
  • A surpreendente expressividade do não determinísmo. Os exemplos de $\frac12L$ e $rot(L)$.
14-04-2020 (Aula 13)
Stacks Image 259
  • Autómatos de Pilha (PDA$ determinísticos e não determinísticos.
  • Exemplo de PDA para $\{0^n1^n\mid n\in\mathbb{N}\}$, $\{w\#w^R\}$ e para $\{w\mid w=w^R\}$
  • Equivalência entre PDAs por pilha vazia e PDAs por estados finais.
17-04-2020 (Aula 14)
Stacks Image 270
  • Gramáticas Independentes de Contexto (CFG)
  • Noção de derivação de uma CFG
  • Propriedades das CFL
  • CFG lineares
21-04-2020 (Aula 15)
Stacks Image 281
  • Árvores de derivação.
  • Noção de gramática ambígua e de linguagem ambígua.
  • Desambiguamento de gramáticas
24-04-2020 (Aula 16)
Stacks Image 292
  • Forma Normal de Chomsky
28-04-2020 (Aula 17)
Stacks Image 303
  • O algoritmo de parsing de Cocke-Younger-Kasimi (CYK)
05-05-2020 (Aula 18)
Stacks Image 314
  • Lema da Repetição para linguagens independentes do contexto
05-05-2020 (Aula 19)
Stacks Image 325
  • Lema de Ogden
12-05-2020 (Aula 20)
Stacks Image 336
  • Fecho das CFL para a reunião concatenação e fecho de Kleene
  • Fecho das CFL para a intersecção com uma linguagem regular
  • Fecho das CFL para as substituições independentes de contexto e para a imagem inversa de homomorfismos.
  • Algoritmo de detecção de uma CFG vazia ou finita
  • As CFL não são fechadas para a intersecção nem para a complementação
15-05-2020 (Aula 21)
Stacks Image 347
  • Equivalência entre a classe das linguagens definidas por autómatos de pilha (PDA) e por gramáticas independentes do contexto (CFG).
19-05-2020 (Aula 22)
Stacks Image 358
  • Máquinas de Turing.
  • Existência de linguagens que não são decidíveis por Máquinas de Turing.
22-05-2020 (Aula 23)
Stacks Image 369
  • Exemplos de Máquinas de Turing
26-05-2020 (Aula 24)
Stacks Image 380
  • 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
29-05-2020 (Aula 25)
Stacks Image 391
  • Uma linguagem não decidível (o Halting Problem)
  • Uma linguagem não reconhecível
  • Referência ao teorema de Rice
  • Máquinas de Turing de comprimento mínimo e suas consequências
  • Breve referência à complexidade de Kolmogorov

Última modificação: 27/11/2021