Hat in einem DFA jeder Staat einen Übergang für jedes Symbol des Alphabets?

12

Wenn nicht, dann , was bedeutet es , wenn aus irgendeinem Zustand und einige Symbole ein , δ ( q , a ) nicht existiert?qeinδ(q,ein)

Duncan
quelle
Ich würde einen nichtdeterministischen Automaten nennen, der niemals mehr als einen Übergang für denselben Zustand und ein deterministisches Eingabesymbol aufweist. Es passt einfach nicht zur DFA-Definition.
Reinierpost
1
Wenn die Regelung eines DFA sind so angeordnet , dass sie nie in Zustand sein kann , q , wenn das Symbol auf dem Band ist ein , tun wir wirklich brauchen , zu definieren δ (q, a) ?
Peter Shor
4
Die Antwort ist klar, dass es davon abhängt, wie man "deterministischen endlichen Automaten" definiert. Daher bin ich mir nicht sicher, ob diese Frage vollständig konstruktiv ist, da es keine allgemein akzeptierte richtige Antwort gibt - dh diese Frage bittet um Meinung und Debatte.
Patrick87
1
Wenn eine Funktion sein soll , muss es für alle Paare q , a definiert werden . δq,ein
vonbrand
In meiner Vorstellung von einem DFA ist dies eine "Abbruch" -Zustand oder wenn Sie einen impliziten Sprung in einen "Ablehnungs" -Zustand bevorzugen.
Yves Daoust

Antworten:

22

Sie scheinen über ein umstrittenes Thema gestolpert zu sein. Anscheinend streiten Informatiker gern. Ich mag es sicherlich zu streiten, also geht es los!

Meine Antwort ist eindeutig: Nein. Deterministische endliche Automaten benötigen nicht für jedes Symbol einen Übergang von jedem Zustand. Die Bedeutung, wenn δ(q,ein) nicht existiert, ist einfach, dass der DFA die Eingabezeichenfolge nicht akzeptiert.

Während Sie eine Definition von DFA erstellen können, die erfordert, dass δ(q,ein) existiert, ist es einfach nicht so, dass ein fehlender Übergang die resultierende Struktur (wie auch immer Sie sie nennen) in irgendeiner Weise nicht deterministisch macht, wie es viele der Kommentatoren sind behaupten. Wenn Sie einen Kurs über Automatentheorie belegen, sind kontextfreie Sprachen und Push-Down-Automaten das nächste Thema, bei denen die Unterscheidung zwischen nichtdeterministischen und deterministischen Automaten kritisch ist und Sie die korrekte Definition des Nichtdeterminismus verwenden müssen.

Nichtdeterminismus ist mit mehr als einem Rechtsübergang verbunden.

Ich denke, wir sind uns alle einig mit der folgenden Wikipedia-Definition (die ich gleich zeigen werde, ist etwas mehrdeutig):

Ein deterministischer endlicher Automat M. ist ein 5-Tupel ( Q. , Σ , δ , q0 , F. ), bestehend aus

  1. eine endliche Menge von Zuständen ( Q. )
  2. eine endliche Menge von Eingabesymbolen, die als Alphabet bezeichnet werden ( Σ )
  3. eine Übergangsfunktion ( δ::Q.×ΣQ. )
  4. ein Startzustand ( q0Q.)
  5. eine Menge von Akzeptanzzuständen ( F.Q. ).

Sei w=ein1ein2einn eine Zeichenkette über dem Alphabet Σ . Der Automat M. akzeptiert die Zeichenkette w wenn eine Folge von Zuständen r0,r1,,rn in Q. mit den folgenden Bedingungen existiert:

  1. r0=q0
  2. rich+1=δ(rich,einich+1) , fürich=0,,n- -1
  3. rnF. .

Die Mehrdeutigkeit und die Kontroverse betrifft die Definition der Übergangsfunktion δ (Nummer "3" in der ersten Liste mit Aufzählungszeichen). Wir sind uns alle einig, dass das, was einen DFA von einem NFA unterscheidet, darin besteht, dass δ eher eine Funktion als eine Beziehung ist . Aber ist δ eine Teilfunktion oder eine Gesamtfunktion ?

Die Definition des DFA funktioniert einwandfrei, wenn δ eine Teilfunktion ist. Wenn Sie bei einer Eingabezeichenfolge einen Zustand qich mit einem Eingabesymbol einj in dem es keinen nächsten Zustand gibt, akzeptieren die Automaten dies einfach nicht.

Wenn Sie diese Definition erweitern, um die Definition von Pushdown-Automaten zu erstellen, müssen Sie außerdem unterscheiden, dass Pushdown-Automaten mit Übergangsfunktionen, die Teilfunktionen sind, als deterministisch und nicht als nicht deterministisch klassifiziert werden.

Wenn Sie die Teilfunktion stört, dann ist hier eine triviale Transformation, die δ einer Gesamtfunktion macht. (Diese Transformation ähnelt nicht dem Teilmengenkonstruktionsalgorithmus, sie fügt höchstens O (1) -Zustände hinzu, ist in der ursprünglichen Anzahl von Zuständen linear und kann auf die Arbeit mit PDAs erweitert werden. Keine dieser Tatsachen trifft auf den Teilmengenkonstruktionsalgorithmus zu .)

  1. füge einen Zustand qerrÖr
  2. Definieren Sie für jedes Paar (qich,sj) bei dem δ undefiniert ist, δ(qich,sj)=qerrÖr .

Diese Automaten haben ein δ , das eine Gesamtfunktion ist und genau die gleichen Zustände akzeptiert und ablehnt, die Ihre ursprünglichen Automaten akzeptiert und abgelehnt haben.

Bearbeiten, Januar 2019

Der Kommentator @Alex Smart kritisiert mich zu Recht dafür, dass ich weder Referenzen gebe noch erkläre, warum wir uns darum kümmern sollten. Also los geht's:

Der Grund , warum wir kümmern vs Nicht-Determinismus über die genaue Definition des Determinismus ist, dass einige Klassen von nicht-deterministischen Automaten mächtiger sind als ihre determinis Cousins, und einige Klassen von nicht-deterministischen Automaten sind nicht mächtiger als ihre determinis Cousins. Für endliche Automaten und Turingmaschinen sind die deterministischen und nicht deterministischen Varianten von gleicher Leistung. Für Pushdown-Automaten gibt es Sprachen, in denen die Unterscheidung wichtig ist: Es gibt NPDA, die die Sprache akzeptieren, und kein DPDA akzeptiert die Sprache. Für die linear begrenzten Automaten ist die Frage offen (oder war das letzte Mal, als ich sie überprüft habe). Die Steigerung der Leistung von NPDA gegenüber DPDA ergibt sich aus der Zulassung mehrerer Übergänge, nicht vom Umschalten der Übergangsfunktion von einer Gesamtfunktion zu einer Teilfunktion.

Bücher aus der Compiler-Community:

Aho und Ullman, Principles of Compiler Design , 1977: Definiert zuerst NFA (Seite 88) mit einer Übergangsbeziehung, dann (S. 90-91):

Wir sagen, ein endlicher Automat ist deterministisch, wenn 1. Er hat keine Übergänge bei der Eingabe ϵ . 2. Für jeden Zustand s und Eingangssymbol ein , gibt es höchstens eine Kante markiert ein Verlassen s .

Aho, Sethi und Ullman, Compiler, Prinzipien, Techniken und Werkzeuge , Nachdruck 1988, ist ähnlich, es definiert zuerst NFA mit einer Übergangsbeziehung, dann (S. 115-116):

Eine deterministische endliche Automatik (kurz DFA) ist ein Sonderfall eines nicht deterministischen endlichen Automaten, in dem ... es höchstens eine Kante gibt, die ein Verlassen von s .

(Beachten Sie, dass @Alex Smart in den Kommentaren sagt: "Der Drache erwähnt ausdrücklich, dass die Funktion vollständig ist." Ich gehe davon aus, dass er mit Co-Autor Lam über die spätere Ausgabe spricht, auf die ich derzeit keinen Zugriff habe. )

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

In einem deterministischen endlichen Automaten (DFA) sind keine zwei Kanten, die aus demselben Zustand austreten, mit demselben Symbol gekennzeichnet.

Appel erklärt dann weiter, dass wir bei der Verwendung von DFA zum Erkennen der längsten Übereinstimmungen explizit die fehlenden Übergänge verwenden, um zu entscheiden, wann gestoppt werden soll (S. 23):

Wenn ein toter Zustand (ein nicht endgültiger Zustand ohne Ausgabeübergänge) erreicht ist, geben die Variablen [die die längste Übereinstimmung aufzeichnen, die wir bisher gesehen haben] an, welches Token abgeglichen wurde und wo es endete.

Bücher aus der Community der Switching-Theorie:

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

Da ein Zustandsdiagramm eine deterministische Maschine beschreibt, muss der nächste Zustandsübergang eindeutig durch den aktuellen Zustand und das gegenwärtig gescannte Eingabesymbol bestimmt werden.

Ich würde normalerweise eindeutig interpretieren , um "genau eins" zu bedeuten, nicht "nicht mehr als eins". (Dh Kohavi scheint zu sagen, dass Determinismus eine Gesamtfunktion erfordert)

Bücher aus der Theorie-der-Berechnung-Community:

Hier scheint es üblicher zu sein, DFAs vor NFAs zu definieren und zu verlangen, dass DFAs eine Gesamtübergangsfunktion haben, dann aber NPDAs vor DPDAs definieren und "Determinismus" als Einschränkung der Übergangsbeziehung auf nicht mehr als definieren -ein Eintrag für jedes Status / Symbol-Paar.

Dies gilt für Hopcroft und Ullman, 1979, Lewis und Papadimitriou, 1981, und insbesondere für Sipser, 2006, der die Definition von DFA pädagogisch verwendet, um genaue formale Definitionen einzuführen, ihre Bedeutung zu erläutern und ausdrücklich zu sagen (S.36):

Die Übergangsfunktion δ gibt genau einen nächsten Zustand für jede mögliche Kombination eines Zustands und eines Eingabesymbols an.

Dies scheint der historischen Entwicklung zu folgen. Deterministische endliche Automaten wurden in den 40er und 50er Jahren eingeführt. Nicht determinierte endliche Automaten wurden in der Arbeit von Rabin und Scott eingeführt: "Endliche Automaten und ihre Entscheidungsprobleme, IBM J. Rsrch und Dvpt , 3 (2): 114-125, 1959. Nach früheren Autoren definieren Rabin und Scott deterministisch endliche Automaten (die sie gewöhnliche Automaten nennen) mit einer Übergangsfunktion "definiert auf dem kartesischen Produkt s×Σ aller Paare von Zuständen und Symbolen" (was ich als Gesamtfunktion interpretieren würde).

Interessanterweise definieren Rabin und Scott auch nicht deterministische endliche Automaten als Gesamtfunktion! Seite 120, Definition 9:

Ein nichtdeterministischer (endlicher) Automat ... ist ein System, in dem ... M. eine Funktion [!] Von S.×Σ mit Werten in der Menge aller Teilmengen von S. .

Das heißt: Die Übergangsfunktion, die total ist, macht das System nicht deterministisch!

Sipser 2006 folgt Rabin und Scott und verwendet für seine Definitionen von nicht deterministischen endlichen Automaten, nicht deterministischen PDAs und nicht deterministischen Turing-Maschinen eine Gesamtübergangsfunktion von Zuständen / Symbolen zum Potenzsatz von Zuständen, überspringt jedoch das Thema deterministisch PDA.

Sowohl Hopcroft und Ullman, 1979, als auch Lewis und Papadimitriou, 1981, verwenden Teilfunktionen in ihren Definitionen deterministischer PDAs. Sie definieren zuerst NPDAs mit einer Übergangsbeziehung, und wenn sie dann zu PDAs kommen, sagen Lewis und Papadimitriou (S. 135):

Ein Pushdown-Automat ist intuitiv deterministisch , wenn für jede Konfiguration höchstens ein Übergang anwendbar ist.

Während Hopcroft und Ullman sagen (S. 112):

Der PDA ... ist deterministisch in dem Sinne, dass von jeder ID höchstens eine Bewegung möglich ist.

Wanderlogik
quelle
qerrÖr
2
Die Teilfunktionsversion ist die in Hopcroft und Ullman angegebene, wenn dies einen Unterschied macht. Die Vorstellung, dass eine Teilfunktion von Natur aus nicht deterministisch ist, ist also keineswegs Standard.
Jmite
1
@jmite Es ist nicht so, dass Teilfunktionen Nichtdeterminismus implizieren; Es ist so, dass Gesamtfunktionen Determinismus implizieren, der Gesamtfunktionen zur besseren Wahl macht. Natürlich ist es eine mehr oder weniger willkürliche Angelegenheit der Definitionen, die Sie verwenden.
Patrick87
3
δ
1
Wie Sie gezeigt haben, hat die Teilfunktionsversion eine einfache Übersetzung in die Gesamtfunktionsversion, und soweit ich sehen kann, gewinnen Sie absolut nichts, weder pädagogisch noch auf andere Weise, indem Sie zulassen, dass die Übersetzungsfunktion partiell ist. Der Drache erwähnt ausdrücklich, dass die Funktion total ist. Warum in aller Welt schaffen wir ein Argument für etwas, das in einem Standardlehrbuch klar definiert wurde und dem die meisten Menschen folgen, wenn es absolut nichts zu gewinnen gibt, wenn sie eine nicht standardmäßige Definition wählen?
Alex Smart
8

δ(q,ein)qQ.einΣQ.Σ

ε

In Bezug auf die Berechenbarkeit entsprechen NFAs DFAs - es gibt einen Algorithmus zum Konvertieren von einem NFA in einen DFA, und ein DFA ist nur trivial ein NFA, der keinen Nichtdeterminismus verwendet, sodass beide die Menge der regulären Sprachen definieren.

Luke Mathieson
quelle
2
Dies hängt von der Definition ab; Es gibt mehrere, deren Leistung gleichwertig ist.
Raphael
3
+1 Halten Sie sich am besten an diese Definition, IMHO, da jeder zustimmen würde, dass ein FA, der genau einen Übergang für jedes (Status-, Symbol-) Paar definiert, einen gültigen DFA darstellt.
Patrick87
1
Und diese Definition ist völlig falsch, wenn Sie versuchen, sie auf die Entscheidung auszudehnen, ob eine kontextfreie Sprache deterministisch oder nicht deterministisch ist. Pushdown-Automaten mit fehlenden Übergängen können immer in Pushdown-Automaten mit genau einem Übergang pro Status / Eingabesymbol / Stapelsymbol umgewandelt werden. Nichtdeterministische Pushdown-Automaten mit mehreren möglichen Übergängen pro Status / Eingabesymbol / Stapelsymbol können nicht unbedingt in deterministische Pushdown-Automaten umgewandelt werden. (Zum Beispiel: für den Fall, dass die erkannte Sprache nicht deterministisch kontextfrei ist.)
Wandering Logic
2
@jmite Definieren Sie einfach Trimmautomaten unabhängig von DFAs. Ich denke, es ist viel wichtiger, dass minimale DFAs die richtige Anzahl von Zuständen gemäß dem Myhill-Nerode-Theorem haben, die Sie nur mit toten Zuständen erhalten.
Patrick87
4
ϵϵϵ
6

Es gibt Definitionen von DFA in Anlehnung an

EIN|δ(q,ein)|1qeinδ(q,ε)δ(q,ein)=einΣEIN

In diesem Fall benötigen Sie nicht alle Übergänge. Wenn der Automat keinen Übergang hat, der zum nächsten Eingabesymbol passt, wird er abgelehnt.

Es ist eine schöne Übung zu zeigen, dass beide Definitionen hinsichtlich der akzeptierten Sprachen gleichwertig sind.

Raphael
quelle
Ich denke, die Frage des OP muss bearbeitet werden, um die formale Definition von DFA aufzunehmen.
Scaaahu
0

In der Definition von DFA sollte jeder Staat das gesamte Alphabet in £ haben. Für ein Beispiel, wenn £ = {a, b, c} und Q = {q0, q1, q2}, sollten alle diese Zustände alle a, b, c-Symbole haben, die in einen anderen Zustand oder denselben Zustand übergehen.

Hasee Amarathunga
quelle
1
Was ist der Unterschied zu vorhandenen Antworten, sodass Sie eine neue Antwort veröffentlichen?
xskxzr
0

Die einfachste Antwort dafür ist, fügen Sie tot Zustand für linkes Symbol . Wie bei der Konvertierung von NFA zu DFA erhalten wir für einige Symbole den Übergang Φ, was bedeutet, dass wir dafür den Dead-Status erstellen.

Niks
quelle