Convertendo um NFA em regex usando o algoritmo GNFA?

Então, eu tenho tentado resolver isso por um longo tempo e quase sinto que estou dando voltas sobre essa questão.

Dado o seguinte NFA:

Usando o algoritmo GNFA, obtenha a expressão regular.

Entendo que você teria o seguinte para a primeira etapa (adicionando estados vazios):

O próximo passo seria remover o estado [q1] que eu obteria:

Por fim, remover [q2] obteria:

No entanto, as respostas que outras pessoas obtiveram são: $(a \cup bb^*a)^*bb^*$ O que não faz sentido como eu entendi, $a^*b(b \cup aa^*b)^*$? Um GNFA (autômato finito não determinístico generalizado) é descrito da seguinte maneira:

Um GNFA é semelhante a um NFA, mas deve obedecer a certas regras:

• Tem apenas um estado de aceitação
• O estado inicial não possui transições.
• O estado de aceitação não tem transições saindo dele
• Uma transição pode denotar qualquer expressão regular, em vez de apenas um símbolo do alfabeto Observe que um símbolo é um tipo de expressão regular.

Além disso, podemos converter um NFA em um GNFA da seguinte maneira:

• Adicione um novo estado inicial com uma transição ε para o antigo estado inicial
• Adicione um novo estado de aceitação com transições ε dos antigos estados de aceitação
• Se as setas tiverem vários rótulos ou se houver várias setas entre dois estados, substitua-as pela união (ou) desses rótulos

Você quer saber por que "os outros" obtiveram uma expressão diferente?

Ao contruir uma expressão regular, não há resposta correta exclusiva. Geralmente existem várias expressões "que fazem sentido". Nesse caso, você usa o método de eliminação de estado (eu aprendi isso com o nome de Brzozowski e McCluskey). Aqui, a ordem de remoção determina a expressão encontrada. Então: o que você ganha ao remover$q2$ primeiro?

Você também pode fazer "truques inteligentes" durante a construção. No seu exemplo você tem$b\cup aa^*b$ que é equivalente a $a^*b$.