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

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.

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 . $M$$A^*$$u, v \in M$$u, uv \in M$$v \in M$

Vorschlag . Sei eine reguläre Teilmenge von A ∗ . Die folgenden Bedingungen sind gleichwertig:$L$$A^*$

1. ist ein recht einheitliches Submonoid,$L$
2. für einen Präfixcode$L = P^*$$P$ ,
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:$L$$A^*$

1. ist ein freies Submonoid von A ∗ ,$L$$A^*$
2. für einen Code C ,$L = C^*$$C$
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 .$L$$A^*$

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.$r^∗$$r$$r^*$

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.$q_0, \ldots, q_n$$q_0 = q_n$$n = 0$$q_0$

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

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.