Revision as of 17:19, 9 February 2015

Tópicos

Análise lexical: expressões regulares, algoritmo de Thompson (construção do NFA), determinização (construção do DFA), minimização de DFA, análise de entrada.

Analisadores lexicais (múltiplas expressões/tokens em simultâneo).

Exercício 1

Para cada uma das expressões regulares seguintes, calcular o autómato finito não-determinista (NFA) pelo algoritmo de Thompson. Para cada um dos casos, calcular o autómato determinista (DFA) mínimo. Em todos os casos, o alfabeto é Σ = { a, b }.

• Exercício 1: (a|b)*
• Exercício 2: (a*|b*)*
• Exercício 3: ((ε|a)b)*
• Exercício 4: (a|b)*abb(a|b)*

Resolução

As ligações acima contêm as soluções para os exercícios propostos.

Procurar resolver sem consultar.