Rogério Reis

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 qiociente 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\), temos que \(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