Une langue peut-elle avoir plusieurs DFA?

17

Par exemple, lorsque nous considérons un DFA qui autorise les chaînes n'ayant aucune sous-chaîne 00ou 11je peux produire les deux DFA suivants:

entrez la description de l'image ici

automata finite-automata Madhuri
la source

Réponses:

37

Tout d'abord, votre DFA gauche est incorrect - il accepte par exemple 011.

Deuxièmement, les DFA peuvent être canoniquement minimisés , donc dans ce sens, vous pouvez toujours trouver un DFA canonique pour une certaine langue.

Mais en général, il existe une infinité de DFA différents pour chaque langue, vous pouvez donc obtenir différentes réponses correctes.

Shaull
la source
Et c'est même infiniment nombreux jusqu'à l'isomorphisme.
G. Bach
Pour être encore plus précis: c'est infini jusqu'à l'isomorphisme lorsque les états sont un sous-ensemble d'un ensemble fixe, par exemple . Si nous ne réglons pas cela, la collection d'automates n'est même pas un ensemble ... D'une manière ou d'une autre, je ne pense pas que c'était l'intention de l'OP :)N
Shaull
Une infinité de DFA différents, même pour des langues finies?
Bergi
1
@Bergi: Certainement - vous pouvez ajouter autant d'états redondants que vous le souhaitez. Cela peut sembler "idiot", et il est en effet insensé lorsque vous construisez vous-même un automate. Cependant, plusieurs fois, les automates sont construits en traduisant à partir d'un autre formalisme (par exemple, la détermination des NFA), auquel cas vous êtes très susceptible d'obtenir des états redondants.
Shaull
@Shaull: Vous voulez dire avec des transitions ε ou des états inaccessibles? OK, je n'y ai pas pensé.
Bergi