Rogério Reis


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

Sumários

Aula 1 (16+20/02/2024)
  • 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.
  • Noção de prefixo, sufixo, infixo e reverso de uma palavra.
  • Definição de tamanho de uma palavra.
  • Operações sobre linguagens: reunião (\(L_1\cup L_2\)), concatenação (\(L_1L_2\)) e fecho de Kleene (\(L^\star\)).
  • Propriedades destas operações.
Aula 2 (23+27/02/2024)
  • Expressões regulares. 
  • Semântica das expressões regulares. 
  • Autómatos finitos determinísticos (DFA). 
  • A linguagem definida por um DFA. 
  • 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 (LR) de uma linguagem regular.
Aula 3 (1+5/03/2024)
  • Transformação de um NFA num DFA.
  • O autómato produto. União e intersecção de linguagens regulares representadas por autómatos finitos. 
  • O autómato (NFA) da concatenação de duas linguagens
  • O autómato (NFA) do fecho de Kleene de uma linguagem
  • Noção de quociente de uma linguagem por um símbolo e por uma palavra.
  • Lema de Arden
  • Método de McCluskey-Brzozowski para obtenção de uma expressão regular equivalente a um autómato.
  • Derivadas de uma expressão regular de Brzozowski
  • O autómato de Brzozowski de uma expressão regular
Aula 4 (8+12/03/2024)
  • Noção de quociente de uma linguagem por uma palavra
  • Relações invariantes à direita
  • Teorema de Myhill-Nerode
  • Autómato determinístico mínimo
  • Algoritmo de minimização de Moore
Aula 5 (15+19/03/2024)
  • Demonstração que \(\{a^nb^n\mid n\in\mathbb{N}\}\) não é regular
  • "Lema da Repetição"
  • Exemplos de utilização do Lema da Repetição
  • Processos de decisão para problemas sobre linguagens regulares
    • Reconhecimento de uma linguagems vazia
    • Reconhecimento de uma linguagem universal
    • Igualdade de linguagens
    • Inclusão de linguagens
Aula 6(05+09/04/2024)
  • Substituições regulares e homomorfismos (morfismos)
  • Fecho das linguagens regulares para substituições regulares e morfismos
  • Fecho das linguagens regulares para a imagem recíproca de morfismos.
  • Quociente direito de uma linguagem \(L_1\) por uma linguagem \(L_2\): \(L_1/L_2\).
  • Fecho de linguagens regulares pelo quociente direito por outra qualquer linguagem.
  • Para qualquer linguagem \(L\), \(P2(L)\) \(\frac12L\) e \(ROT(L)\) também são regulares.
Aula 7(12+16/04/2024)
  • Linguagens Independentes de Contexto (CFL)
  • Autómatos de pilha (PDA), suas configurações e linguagens associadas
  • Gramáticas independentes de contexto (CFG) e linguagens por elas reconhecidas.
  • Gramáticas lineares (à esquerda e à direita) e transformação de um DFA numa CFG.
  • Derivações pela esquerda e derivações pela direita.
  • Árvores de derivação.
  • Fecho das CFL para a união, a concatenação, o fecho de Kleene e o reverso.
Aula 8 (19+23/04/2024)
  • Gramáticas ambíguas
  • Linguagens ambíguas
  • Exemplos de desambiguação de gramáticas
  • Forma Normal de Chomsky (CNF) de uma gramática.
Aula 9 (26+30/04/2024)
  • Transformação de PDA em CFG.
  • Transformação de CFG em PDA.
  • As CFL são fechadas para substituições independentes de contexto.
  • A imagem directa e recíproca de uma CFL por um morfismo continua a ser uma CFL.
Aula 10 (3+14/05/2024)
  • Lema da repetição para Linguagens Independentes de Contexto
  • As CFL unárias são regulares
  • Lema de Ogden para Linguagens Independentes de Contexto
  • Existência de CFLs intrinsecamente ambíguas
Aula 11 (17+21/05/2024)
  • O algoritmo de "parsing" CYK
  • Problemas decidíveis para CFLs:
    • CFL vazia
    • CFL finita
  • Existência de (muitas) linguagens não descritíveis por qualquer modelo finito
Aula 12 (24+28/05/2024)
  • Maquinas de Turing (TM)
  • Equivalência entre os diversos modelos de TM sob o ponto de vista da computabilidade
  • Linguagens Decidíveis, Reconhecíveis
  • Existência de linguagens não reconhecíveis

Última modificação: 06/04/2025