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: 20/05/2025