Rogério Reis


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

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