Kann eine Sprache mehr als einen DFA haben?

17

Wenn zum Beispiel betrachten wir einen DFA , die die Saiten haben weder Sub - Strings erlaubt 00oder 11ich kann die folgenden zwei DFAs produzieren:

Bildbeschreibung hier eingeben

automata finite-automata Madhuri
quelle

Antworten:

37

Erstens ist Ihr linker DFA falsch - er akzeptiert zB 011.

Zweitens können DFAs kanonisch minimiert werden. In diesem Sinne finden Sie immer einen kanonischen DFA für eine bestimmte Sprache.

Im Allgemeinen gibt es unendlich viele verschiedene DFAs für jede Sprache, sodass Sie unterschiedliche richtige Antworten erhalten können.

Shaull
quelle
Und das sind sogar unendlich viele bis hin zum Isomorphismus.
G. Bach
N
Unendlich viele verschiedene DFAs, auch für endliche Sprachen?
Bergi
1
@Bergi: Natürlich - Sie können so viele redundante Zustände hinzufügen, wie Sie möchten. Das mag "albern" klingen, und es ist in der Tat sinnlos, wenn Sie selbst einen Automaten bauen. Häufig werden Automaten jedoch durch Übersetzen aus einem anderen Formalismus (z. B. Bestimmen von NFAs) erstellt. In diesem Fall ist es sehr wahrscheinlich, dass Sie redundante Zustände erhalten.
Shaull
@Shaull: Du meinst mit ε-Übergängen oder unerreichbaren Zuständen? OK, ich habe nicht darüber nachgedacht.
Bergi