Conversão de uma expressão regular num AFND

Para compreendermos minimamente a construção de analisadores léxicos só falta abordarmos o problema da conversão automática de expressões regulares para autómatos.

Para esse fim vamos apresentar um algoritmo (McNaughton-Yamada-Thompson) que converte uma qualquer ER num AFND.

A estratégia baseia-se no seguinte:

• Ter AFND definidos para ER elementares;

• Ter padrões para AFND resultantes das operações sobre ER (reunião, concatenação, fecho de Kleene, . . . , . . . ).

• Construir o AFND recorrendo à árvore sintáctica da ER.

A tabela seguinte mostra os padrões para AFND de ER

Conversão de uma ER num AFND: Exemplo

Vamos então construir um AFND para a ER: (a|b)*abb

A árvore sintáctica desta ER é a seguinte: