Ein deterministischer endlicher Automat (DFA) ist ein Zustandsmaschinenmodell, das alle und nur reguläre Sprachen akzeptieren kann. DFAs können (und werden in der Regel) so definiert, dass jeder Status einen Übergang für alle Elemente des Eingabealphabets bereitstellen muss. Mit anderen Worten, die Übergangsfunktion sollte eine (Gesamt-) Funktion sein.
Stellen Sie sich vor, was wir einen doppelt deterministischen endlichen Automaten (DDFA) nennen werden. Es wird ähnlich wie ein DFA definiert, mit zwei Ausnahmen: Erstens muss der Übergang, der für jedes mögliche Eingabesymbol von einem Zustand in einen anderen Zustand führt, zu zwei unterschiedlichen Zuständen führen. Zweitens müssen alle potenziellen Pfade eine der folgenden Bedingungen erfüllen, um eine Zeichenfolge zu akzeptieren:
- Alle möglichen Pfade durch den DDFA führen zu einem akzeptierenden Zustand (wir werden dies einen DDFA vom Typ 1 nennen).
- Alle potenziellen Pfade durch den DDFA führen zu demselben akzeptierenden Zustand (wir werden dies einen DDFA vom Typ 2 nennen).
Nun zu meiner Frage:
Welche Sprachen akzeptieren DDFAs des Typs 1 und 2? Insbesondere ist es der Fall, dass , oder ? In dem Fall, dass , gibt es eine einfache Beschreibung von ?
Beweise (oder zumindest mäßig ausgearbeitete Skizzen) werden geschätzt, wenn sie nicht zu kompliziert sind.
quelle