Dans un DFA, chaque état a-t-il une transition sur chaque symbole de l'alphabet?

Sinon, qu'est-ce que cela signifie quand pour un état et un symbole , n'existe pas?a δ ( q , a $q$$a$$\delta(q, a)$

Vous semblez être tombé sur une question litigieuse. Apparemment, les informaticiens aiment discuter. J'aime certainement discuter, alors voilà!

Ma réponse est sans équivoque: Non. Un automate fini déterministe n'a pas besoin d'une transition de chaque état pour chaque symbole. La signification lorsque n'existe pas est simplement que le DFA n'accepte pas la chaîne d'entrée.$\delta(q,a)$

Bien que vous puissiez créer une définition de DFA qui nécessite que existe, il n'est tout simplement pas le cas qu'une transition manquante rende la structure résultante (quel que soit votre nom) de quelque manière non déterministe que la plupart des commentateurs. réclament. Si vous suivez un cours sur la théorie des automates, le sujet suivant sera les langages sans contexte et les automates déroulants où la distinction entre automates non déterministes et déterministes est critique, et vous devez utiliser la définition correcte du non-déterminisme.$\delta(q,a)$

Le non-déterminisme est associé à plus d'une transition juridique.

Je pense que nous sommes tous d'accord avec la définition de Wikipédia suivante (que je montrerai dans une seconde est légèrement ambiguë):

Un automate fini déterministe est un tuple 5 ( , , , , ), composé de$M$$Q$$\Sigma$$\delta$$q_0$$F$

1. un ensemble fini d'états ( )$Q$
2. un ensemble fini de symboles d'entrée appelé l'alphabet ( )$\Sigma$
3. une fonction de transition ( )$\delta : Q \times \Sigma \rightarrow Q$
4. un état de départ ($q_0 \in Q)$
5. un ensemble d'états d'acceptation ( ).$F \subseteq Q$

Soit une chaîne sur l'alphabet . L'automate accepte la chaîne si une séquence d'états, , existe dans avec les conditions suivantes:$w = a_1 a_2 \cdots a_n$$\Sigma$$M$$w$$r_0, r_1, \ldots, r_n$$Q$

1. $r_0 = q_0$
2. $r_{i+1} = \delta(r_i, a_{i+1})$ , pour$i = 0, \ldots, n−1$
3. $r_n \in F$ .

L'ambiguïté et la controverse portent sur la définition de la fonction de transition, (numéro "3" dans la première liste à puces.) Nous convenons tous que ce qui différencie un DFA d'un NFA est que est une fonction plutôt qu'un relation . Mais une fonction partielle ou une fonction totale ?$\delta$δ δ$\delta$$\delta$

La définition du DFA fonctionne très bien si est une fonction partielle. Étant donné une chaîne d'entrée, si vous atteignez un état avec un symbole d'entrée où il n'y a pas d'état suivant, les automates n'acceptent tout simplement pas.$\delta$$q_i$$a_j$

De plus, lorsque vous étendez cette définition pour créer la définition des automates déroulants, vous devrez faire la distinction que les automates déroulants avec des fonctions de transition qui sont des fonctions partielles sont classés comme déterministes, non non déterministes.

Si la fonction partielle vous dérange alors voici une transformation triviale qui fait de une fonction totale. (Cette transformation n'est pas comme l'algorithme de construction de sous-ensemble, elle ajoute au plus des états O (1), est linéaire dans le nombre d'états d'origine et peut être étendue pour fonctionner avec des PDA. Aucun de ces faits n'est vrai de l'algorithme de construction de sous-ensemble .)$\delta$

1. ajouter un état$q_{\mathrm{error}}$
2. pour chaque paire où n'est pas défini, définissez .$(q_i, s_j)$$\delta$$\delta(q_i, s_j) = q_{\mathrm{error}}$

Ces automates ont un qui est une fonction totale et accepte et rejette exactement le même ensemble d'états que vos automates originaux ont accepté et rejeté.$\delta$

Edit, janvier 2019

Le commentateur @Alex Smart me critique à juste titre pour ne pas avoir donné de références, ni pour expliquer pourquoi nous devrions nous en soucier. Alors voilà:

La raison pour laquelle nous nous soucions de la définition exacte du déterminisme par rapport au non-déterminisme, est que certaines classes d'automates non déterministes sont plus puissantes que leurs cousines déterministes, et certaines classes d'automates non déterministes ne sont pas plus puissantes que leurs cousines déterministes. Pour les automates finis et les machines de Turing, les variantes déterministes et non déterministes ont une puissance équivalente. Pour les automates à refoulement, il existe des langues où la distinction est importante: il existe des NPDA qui acceptent la langue et aucun DPDA n'accepte la langue. Pour les automates délimités linéaires, la question est (ou était la dernière fois que j'ai vérifié) ouverte. L'augmentation de la puissance de NPDA par rapport à DPDA vient de permettre à plusieurs transitions, pas de transformer la fonction de transition d'une fonction totale à une fonction partielle.

Livres de la communauté des compilateurs:

Aho et Ullman, Principles of Compiler Design , 1977: définit d'abord NFA (page 88) avec une relation de transition, puis (p. 90-91):

On dit qu'un automate fini est déterministe si 1. Il n'a pas de transitions sur input . 2. Pour chaque état et symbole d'entrée , il y a au plus un bord étiqueté sortant .$\epsilon$$s$$a$$a$$s$

Aho, Sethi et Ullman, Compilers, principes, techniques et outils , réimpression de 1988, est similaire, il définit d'abord NFA avec une relation de transition, puis (p. 115-116):

Un automate déterministe fini (DFA, pour faire court) est un cas particulier d'un automate non déterministe finitie dans lequel ... il y a tout au plus une arête marquée laissant .$a$$s$

(Notez que dans les commentaires @Alex Smart dit, "le dragon mentionne spécifiquement que la fonction est totale." Je suppose qu'il parle de la dernière édition avec le co-auteur Lam, à laquelle je n'ai pas accès pour le moment. )

Appel, Modern Compiler Implementation in Java , 1988 (p. 22):

Dans un déterministe automate fini (DFA), pas deux bords laissant du même état sont étiquetés avec le même symbole.

Appel poursuit en expliquant que lorsque vous utilisez DFA pour reconnaître les correspondances les plus longues, nous utilisons explicitement les transitions manquantes pour décider du moment de l'arrêt (p. 23):

lorsqu'un état mort (un état non final sans transition de sortie) est atteint, les variables [qui enregistrent la plus longue correspondance que nous ayons vue jusqu'à présent] indiquent quel jeton a été mis en correspondance et où il s'est terminé.

Livres de la communauté de la théorie de la commutation:

Kohavi, Switching and Finite Automata Theory, 2 / e , 1978, p. 611 dit:

Étant donné qu'un diagramme d'état décrit une machine déterministe , la transition d'état suivante doit être déterminée uniquement par l'état actuel et le symbole d'entrée actuellement balayé.

J'interprète généralement de manière unique comme signifiant "exactement un", pas "pas plus d'un". (C'est-à-dire que Kohavi semble dire que le déterminisme nécessite une fonction totale)

Livres issus de la communauté de la théorie du calcul:

Ici, il semble plus courant de définir les DFA avant les NFA et d'exiger que les DFA aient une fonction de transition totale, mais ensuite de définir les NPDA avant les DPDA et de définir le «déterminisme» comme étant une restriction de la relation de transition à ne pas avoir plus de -une entrée pour chaque paire état / symbole.

C'est le cas de Hopcroft et Ullman, 1979, Lewis et Papadimitriou, 1981, et, en particulier de Sipser, 2006, qui utilise la définition de DFA de manière pédagogique pour introduire des définitions formelles précises, expliquer leur importance et dire explicitement (p.36):

la fonction de transition, , spécifie exactement un état suivant pour chaque combinaison possible d'un état et d'un symbole d'entrée.$\delta$

Cela semble suivre l'évolution historique. Des automates finis déterministes ont été introduits dans les années 40 et 50. Les automates finis non déterministes ont été introduits dans l'article de Rabin et Scott, "Automates finis et leurs problèmes de décision, IBM J. Rsrch et Dvpt , 3 (2): 114-125, 1959. Suivant les auteurs antérieurs, Rabin et Scott définissent déterministe les automates finis (qu'ils appellent automates ordinaires ) comme ayant une fonction de transition "définie sur le produit cartésien de toutes les paires d'états et de symboles" (que j'interpréterais comme signifiant une fonction totale).$s\times\Sigma$

Fait intéressant, Rabin et Scott définissent également des automates finis non déterministes en termes de fonction totale! Page 120, définition 9:

Un automate non déterministe (de fini) ... est un système où ... est une fonction [!] De avec des valeurs dans l'ensemble de tous les sous - ensembles de .$M$$S\times\Sigma$$S$

C'est-à-dire que la fonction de transition étant totale ne rend pas le système déterministe!

Sipser 2006 suit Rabin et Scott et utilise une fonction de transition totale des états / symboles vers l'ensemble d'états de puissance pour ses définitions des automates finis non déterministes, des PDA non déterministes et des machines de Turing non déterministes, mais saute le sujet déterministe PDA.

Hopcroft et Ullman, 1979, et Lewis et Papadimitriou, 1981 utilisent tous deux des fonctions partielles dans leurs définitions des PDA déterministes. Ils définissent d'abord les NPDA avec une relation de transition, puis lorsqu'ils arrivent aux PDA, Lewis et Papadimitriou disent (p. 135),

Un automate déroulant est déterministe , intuitivement parlant, s'il y a au plus une transition applicable à chaque configuration.

Alors que Hopcroft et Ullman disent (p. 112):

Le PDA ... est déterministe dans le sens où au plus un mouvement est possible à partir de n'importe quel ID.

Comme le note scaaahu dans les commentaires, selon une définition commune, un automate fini déterministe (DFA) doit avoir une transition de chaque état sur chaque symbole de l'alphabet, c'est-à-dire que la fonction de transition est définie pour tout et où est l'ensemble des états et est l'alphabet.$\delta(q,a)$$q \in Q$$a\in \Sigma$$Q$$\Sigma$

Une fois que vous commencez à exclure les transitions ou à ajouter plusieurs transitions sur le même symbole à partir du même état, vous disposez d'un automate fini non déterministe (NFA). Les NFA ont également une possibilité supplémentaire, -transitions, où ils peuvent passer d'un état à un autre sans lire de symbole dans l'entrée.$\varepsilon$

En termes de calcul, les NFA sont équivalents aux DFA - il existe un algorithme pour convertir d'un NFA en DFA, et un DFA est simplement un NFA qui n'utilise aucun non-déterminisme, ils définissent donc tous deux l'ensemble des langages réguliers.

Il existe des définitions de DFA dans le sens de

Si est NFA et pour tous les et (et si , alors pour tous les ) alors est DFA.| δ ( q $A$q a δ ( q , ε ) ≠ ∅ δ ( q , a ) = ∅ a ∈ Σ $|\delta(q,a)| \leq 1$$q$$a$$\delta(q,\varepsilon) \neq \emptyset$$\delta(q,a) = \emptyset$$a \in \Sigma$$A$

Dans ce cas, vous n'avez pas besoin de toutes les transitions. Si l'automate n'a pas de transition correspondant au symbole d'entrée suivant, il rejette.

C'est un bon exercice de montrer que les deux définitions sont équivalentes en termes de langues pouvant être acceptées.

Dans la définition de DFA, tous les États doivent avoir tout l'alphabet en £. Par exemple, si les £ = {a, b, c} et Q = {q0, q1, q2}, tous ces états doivent avoir tous les symboles a, b, c qui passent à un autre état ou au même état.

La réponse la plus simple à cela est que vous ajoutez l' état mort pour le symbole de gauche . Comme lors de la conversion de NFA en DFA, nous obtenons la transion Φ pour certains symboles, ce qui signifie que nous créons pour elle l'état mort.