Minimiser les automates finis déterministes sans états d'acceptation

J'ai un automate fini sans état final / acceptant, donc F est vide. Comment puis-je le minimiser?

J'ai obtenu ceci sur un test et je ne savais pas comment aborder le problème parce que l'automate n'avait aucun état d'acceptation. Un seul état initial avec toutes les transitions en lui-même est-il la bonne réponse?

Votre supposition est correcte et vous pouvez la voir un peu plus formellement comme suit. Laisser$\mathcal{A} = (Q, A, \cdot, q_0, F)$être un DFA. La congruence de Nérode$\sim$ sur $Q$ est défini comme suit:

$$p \sim q \text{ if and only if, for every word $u \in A^*$, }\ p \cdot u \in F \iff q \cdot u \in F$$ L'ensemble des états de l'automate minimal de $\mathcal{A}$ est $Q/{\sim}$. Maintenant si$F$ est l'ensemble vide, tous les états de $Q$ sont $\sim$-équivalent et donc $Q/{\sim}$ n'a qu'un seul élément, disons $Q/{\sim} = \{1\}$. Vous n'avez pas le choix pour les transitions et donc$1 \cdot a = 1$ pour chaque lettre $a$. finalement$1$ est l'état initial, mais il n'y a pas d'état final.

Un automate fini sans états finaux désigne le langage L = $\emptyset$. Pour minimiser un DFA, nous minimisons le nombre d'états et la langue indiquée doit être la même. Par définition de DFA, nous devons avoir un état initial$q_0$ donc $| Q | \geq 1$ et comme vous le dites, nous devons inclure la fonction de transition avec toute transition vers $q_0$ (parce que créer des états morts est contre-productif).