Expresões regulares

  1. Represente o diagrama de estados do autómato finito não determinista (NFA) que se obtém aplicando o algoritmo de Thompson a cada uma das seguintes expressões regulares. Converta para o autómato finito determinista (DFA) e minimize-o:
    1. (a|b)*
    2. (a*|b*)*
    3. ((ø|a)b*)*
    4. (a|b)*abb(a|b)*
  2. Represente o diagrama de estados do autómato finito não determinista (NFA) que se obtém aplicando o algoritmo de Thompson a cada uma das seguintes sequéncias ordenadas de expressões regulares definidas sobre o alfabeto S={a, b}. Converta para o autómato finito determinista (DFA) e minimize-o. Indique para quantos passos são necessários para reconhecer cada sequência de entrada.
    1. G={ab, ab*, a|b} Entrada=abaabb
    2. G={aa, aaaa, a|b} Entrada=aaabaaaaa
    Nota: ø representa a produção nula.