17-09-2026 (1)
- Apresentação da unidade curricular
- Linguagens Regulares e Quocientes esquerdos
- Complexidade determinística por estados (sc)
- Complexidade não determinística por estados (nsc)
- 2DFA e a sua simulação por um DFA
24-09-2026 (2)
- Linguagens locais e a sua relação com as linguagens regulares
- O monoide sintáctico.
- A caracterização das linguagens regulares à custa do monoide sintáctico.
01-10-2026 (3)
- Linguagem reconhecida por um monoide
- Linguagens star-free
- O Teorema de Schützenberger
08-010-2026 (4)
- Linguagens unárias
- A forma normal de Chrobak e o seu custo em termos do número de estados resultante
- Linguagens Independentes do Contexto e a equivalência entre CFGs e PDAs
- Lemas de repetição (Pumping Lemmas):
- Lema da Repetição para linguagens regulares (Rabin & Scott)
- Lema de Jaffe
- Lema de Stanat-Weiss
- Lema da Repetição para CFLs (Bar-Hillel-Perles-Shamir)
- Lema de Ogden
- Prova de um minorante para a complexidade por estados da simulação de um PDA por uma CFG
15-10-2026 (5)
- Conjuntos semilineares
- O teorema de Parikh
- O Teorema da troca condição necessária para uma linguagem ser CFL
- DCFLs
- As DCFL são fechadas para o complemento
- O teste de Knuth para DCFL
- O "Pumping Lemma" de Yu, para DCFLs
22-10-2026 (6)
- Linguagens Lineares e suas caracterizações
- Linguagens "one-turn"
- Linguagens "finite-turn"
- Linguagens "one-counter"
Última modificação: 23/10/2026