Dans l'image ci-dessous puis-je utiliser les deux NFA de manière interchangeable? Si non alors pourquoi?Pouvez-vous ignorer les transitions epsilon dans l'expression de l'union (algorithme de construction de Thompson)
Oui, ils sont équivalents (ils reconnaissent la même langue). Plus formellement:
Tout d'abord, nous allons donner des noms à vos états:
Maintenant, grâce à powerset construction, nous allons supprimer les transitions epsilon:
Enfin, nous pouvons utiliser tout algorithme de minimisation DFA tel que Brzozowski's (inversez les flèches, appliquez de nouveau la construction de l'ensemble de puissance, inversez les flèches) pour obtenir votre DFA résultant.
l'outil que vous utilisez? –