(N) DFA mit den gleichen anfänglichen / akzeptierenden Zuständen

13

Was ist über die Klasse der Sprachen bekannt, die von endlichen Automaten erkannt werden, die denselben Anfangszustand und denselben Akzeptanzzustand haben? Dies ist eine richtige Teilmenge der regulären Sprachen (da jede dieser Sprachen die leere Zeichenfolge enthält), aber wie schwach ist sie? Gibt es eine einfache algebraische Charakterisierung?

Das Gleiche gilt für Sprachen, die von nicht deterministischen Automaten erkannt werden, die den gleichen Satz von Anfangs- und Akzeptanzzuständen haben.

Noam Zeilberger
quelle
13
Angenommen, Sie meinen, dass der Anfangszustand der eindeutige Akzeptanzzustand sein muss, dann entsprechen endliche Automaten mit dieser Struktur den Sprachen der regulären Ausdrücke der Form , wobei r ein regulärer Ausdruck ist. rr
Huck Bennett
Ah, natürlich. Vielen Dank! Wenn Sie diesen Kommentar als Antwort posten möchten, akzeptiere ich ihn und schließe die Frage.
Noam Zeilberger

Antworten:

8

Diese Frage wird für deterministische Automaten und für eindeutige Automaten im Buch gelöst.

[1] J. Berstel, D. Perrin, C. Reutenauer, Codes and Automata, Bd. 129 von Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2009.

Bei deterministischen Automaten ist die Charakterisierung in Satz 3.2.5 angegeben. Daran erinnern , dass ein Untermonoid von A * ist richtig einheitliche , wenn für alle u , v M , u , u v M bedeutet , v M . MAu,vMu,uvMvM

Vorschlag . Sei eine reguläre Teilmenge von A . Die folgenden Bedingungen sind gleichwertig:LA

  1. ist ein recht einheitliches Submonoid,L
  2. für einen Präfixcode PL=PP ,
  3. Der Minimalautomat von hat einen eindeutigen Endzustand, nämlich den Anfangszustand.L
  4. Es gibt einen deterministischen Automaten, der mit dem Anfangszustand als eindeutigen Endzustand erkennt .L

Für eindeutige Automaten folgt die Charakterisierung aus Satz 4.2.2 und kann wie folgt angegeben werden:

Vorschlag . Sei eine reguläre Teilmenge von A . Die folgenden Bedingungen sind gleichwertig:LA

  1. ist ein freies Submonoid von A ,LA
  2. für einen Code C ,L=CC
  3. Es gibt einen eindeutigen Automaten, der mit dem Anfangszustand als eindeutigen Endzustand erkennt .L

Schließlich ist für nichtdeterministische Automaten die Charakterisierung einfach, dass ein Submonoid von A ∗ ist .LA

J.-E. Stift
quelle
1
Es könnte sich lohnen, sich Eilenbergs monomiale Zerlegung von regulären (in seiner Terminologie rationalen) Sprachen nach dem Einheitspräfix anzusehen. Ich habe keine Kopie des Buches bei mir, aber es befindet sich irgendwo in den früheren Abschnitten von Automata, Languages ​​and Machines, Volume A (1974).
gdmclellan
1
@gdmclellan Du hast vollkommen recht. Die genaue Referenz ist Kap. IV, Proposition 3.2.
J.-E.
Können wir in beiden Sätzen hinzufügen, dass und C regulär sind? Dh L = P für einen Präfixcode P, bei dem P als regulär gewählt werden könnte? PCL=PPP
StefanH
14

Endliche Automaten, in denen der Anfangszustand auch der eindeutige akzeptierende Zustand ist, haben die Form , wobei r ein regulärer Ausdruck ist. Als J.-E. Pin weist darauf hin, dass das Gegenteil nicht zutrifft: Es gibt Sprachen der Form r ∗, die von einem DFA mit einem eindeutigen Akzeptanzstatus nicht akzeptiert werden.rrr

Wenn eine Folge von Zuständen so dass q 0 = q n, muss entweder n = 0 oder das zugrunde liegende Zustandsdiagramm einen Zyklus mit q 0 haben . Letzterer Fall wird vom Kleene-Stern algebraisch erfasst.q0,,qnq0=qnn=0q0

Huck Bennett
quelle
2
Die von einem Automaten akzeptierten Sprachen, in denen der Anfangszustand auch der eindeutige Akzeptanzzustand ist, haben mit Sicherheit die Form . Diese Bedingung kennzeichnet jedoch nicht die Sprachen, die von einem solchen DFA akzeptiert werden. Beispielsweise akzeptiert jede DFA die Sprache ( a , a b ) * mindestens 2 Endzustände. r(a,ab)
J.-E.
2
Ich denke , die richtige Charakterisierung ist: durch einen akzeptiert wird minimal DFA dessen Startzustand ist der einzige Staat akzeptieren, wenn und nur wenn L von der Form α * wo α ist Präfix frei . Ich erinnere mich, dass ich dies in einer MS / PhD-Arbeit aus den 70er Jahren gefunden habe, aber ich kann die Referenz nicht finden. Jedenfalls ist es nicht schwer zu beweisen. LLαα
Mikero
@ J.-E.Pin: Ja, danke, ich habe meine Antwort aktualisiert.
Huck Bennett
10

Eine wichtige Unterklasse dieser Familie ist eine Unterklasse von 0-reversiblen Sprachen. Eine Sprache ist 0-reversibel, wenn die Umkehrung des minimalen DFA für die Sprache ebenfalls deterministisch ist. Die Umkehroperation ist definiert als Vertauschen des Anfangs- und Endzustands und Invertieren der Kantenrelation des DFA. Dies bedeutet, dass eine 0-reversible Sprache nur einen akzeptierenden Zustand haben kann. Ihre Frage fügt eine weitere Einschränkung hinzu, dass dieser Zustand der Ausgangszustand sein sollte. Ihre Einschränkung definiert nicht die 0-reversiblen Sprachen, da der minimale DFA für diese Sprachen unterschiedliche Anfangs- und Endzustände haben kann.

Die Klasse der umkehrbaren Sprachen ist interessant, weil sie eine der ersten Sprachfamilien mit unendlich vielen Zeichenfolgen war, die nur anhand von positiven Beispielen erlernbar war. Angluins Arbeit liefert auch eine algebraische Charakterisierung.

Inferenz reversibler Sprachen , Dana Angluin, Journal of the ACM, 1982

Vijay D
quelle
1

Sie können sich auf Halbblumenautomaten beziehen, wie es in ihrem Artikel heißt: "Ein Halbblumenautomat (SFA) ist ein Trimmautomat mit einem eindeutigen Anfangszustand, der gleich einem eindeutigen Endzustand ist, in dem alle Zyklen durchlaufen werden Ausgangszustand ". Siehe "DIE HEILIGE ZERSETZUNG VON KREISFÖRMIGEN HALBBLUMEN-AUTOMATEN" -Shubh Narayan Singh, KV Krishna.

Viresh
quelle