Comment faire pour convertir (ab u aab u aba) * en un NFA?

Question

(ab u AAB u aba) *

je l'ai fait mais je voudrais quelques commentaires sur son exactitude:

Si elle est correcte: Peut-on simplifier (ab u AAB u aba) * tout plus loin?

Si non: Qu'est-ce que j'ai manqué?

EDIT: Il me semble qu'il me manque des transitions électroniques de tous les 3 états finaux à l'état initial et j'ai besoin d'un nouvel état qui est initial et final qui ira à l'ancien état initial sur e-transition. (Règle de Kleene Star).

post-scriptum Peut-on également simplifier (a u b)*aabab et (a u b)*a(a u b)(a u b)(a u b)(a u b).

La raison pour laquelle je demande parce que s'il n'y a pas moyen de simplifier/réduire au minimum, ce sera un ridiculement longue DFA ...

Answer 1

Je peux voir une petite simplification de votre premier cas que vous pouvez l'écrire comme (a (bu ab u ba)) * mais cela n'aide pas nécessairement. Je devinerais encore que votre DFA n'aura pas besoin d'autant d'états que vous le pensez.

Les deux derniers cas nécessiteront des DFA avec 32 états afin de garder une trace des 5 derniers caractères lus. La différence est que le second DFA n'a qu'un seul terminal tandis que le troisième DFA en a 16. 16.