Sumários
18-02-2025
- 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.
- 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$).
21-02-2025
- Expressões regulares.
- Semântica das expressões regulares.
- Propriedades das expressões regulares
- O problema da palavra para expressões regulares
25-02-2025
- Automatos finitos determinísticos (DFA)
- A extensão da função de transições de um DFA de \(\delta:Q\times\Sigma\rightarrow Q\) para \(\delta:Q\times\Sigma^\star \rightarrow Q\)
- A linguagem de um DFA
- Configuração de um DFA
- DFAs completos e não completos
- Exemplos de DFAs
26-02-2025
- 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.
7-03-2025
- 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.
- O autómato (NFA) da concatenação de duas linguagens
- O autómato (NFA) do fecho de Kleene de uma linguagem
11-03-2025
- 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
14-03-2025
- Relações invariantes à direita
- Refinamento de uma relação de equivalência
- Teorema de Myhill-Nerode
18-03-2025 (8)
- Autómato determinístico mínimo
- Algoritmo de minimização de Moore
22-03-2025 (9)
- 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
25-03-2025 (10)
- 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.
28-03-2025 (11)
A conveniência do não-determinismo
Seja \(L\) uma linguagem regular:
\(P2(L)=\{w\mid ww\in L\}\) é regular;
\(\frac12 L=\{w\mid (\exists u) (|u|=|w|\land wu\in L)\}\) é regular;
\(ROT(L)=\{ xy\mid yx\in L\}\) é regular.
01-04-2025 (12)
Autómatos de Pilha (PDA) determinísticos e não determinísticos
04-04-2025 (13)
- 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.
- Fecho das CFL para a união, a concatenação, o fecho de Kleene e o reverso.
11-04-2025 (14)
- Derivações pela direita e pela esquerda
- Árvores de derivação
- Revisões da matéria anterior
22-04-2025 (15)
- Ambiguidade de CFGs e de CFLs
Última modificação: 22/04/2025