Projetando um DFA para um Lexer: nós de caracteres compartilhados vs. separados

Um nó em uma representação DFA corresponde a um estado . Se você quiser representar dois estados distintos, precisará de pelo menos dois nós distintos.

Então, quando sua língua tem as palavras returne func, e você leu até agora ret, você está em um estado diferente do que se tivesse lido f, mesmo que em ambos os estados você tenha uma transição para a letra u. A questão é que, depois de ter processado isso, uvocê ainda deve saber se estava no processo de completar a palavra returnou func, caso contrário, você também aceitaria as palavras furne retunc. Então, não, você não pode considerar esses dois estados como iguais.

Perceba que um estado não se relaciona diretamente com o próximo caractere que você pode aceitar. É mais correto pensar nele como representando o que você já leu.

Então, no seu gráfico DFA, você poderia combinar os nós ie i3em um nó, e então ter duas transições de saída de lá para prosseguir para ifou int. Você já aplicou esse princípio para a letra inicial e, mas poderia ter continuado fazendo isso para o subsequente l(merging l1and l2) e s(merging s1and s2), de modo que a divisão só ocorreria naquele último estado em e(for else) e i(for elsif).