Rogério Reis

• Expressões regulares. 
• Semântica das expressões regulares. 
• Propriedades das expressões regulares
• O problema da palavra para expressões regulares

• 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
• Autómato complementar de um autómato determinístico completo.

• Não determinismo. 
• Autómatos Finitos Não-determinísticos (NFA).
• A extensão da função de transições de um NFA de \(\delta:Q\times\Sigma\rightarrow 2^Q\) para \(\delta:2^Q\times\Sigma^\star\rightarrow 2^Q\).
• A linguagem definida por um NFA. 
• O autómato da linguagem reversa (\(L^R\)) de uma linguagem regular \(L\).
• 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

• 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

• Relações invariantes à direita
• Refinamento de uma relação de equivalência
• Teorema de Myhill-Nerode

• Autómato determinístico mínimo
• Algoritmo de minimização de Moore

• 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

• 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.

A conveniência do não-determinismo

Seja \(L\) uma linguagem regular:

• \(\sqrt{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.

Autómatos de Pilha (PDA) determinísticos e não determinísticos

• 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.

• Forma Normal de Chomsky

• O "parser" CYK

• Lema da repetição para as CFLs
• As CFL não são fechadas para o complemento.