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

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

1. (a|b)*
2. (a*|b*)*
3. ((ε|a)b)*
4. (a|b)*abb(a|b)*

Exercício 2

Para cada uma das seguintes sequências ordenadas 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 }. Indicar em quantos passos é processada a entrada apresentada.

1. G = { ab, ab*, a|b }, entrada = abaabb
2. G = { aa, aaaa, a|b}, entrada = aaabaaaaa

Resoluções

Resoluções destes exercícios podem ser obtidas no wiki da disciplina, na secção sobre aspectos teóricos de análise lexical.