Wie XOR-Automaten?

Angenommen, wir haben 3 DFAs. Wir wissen, wie man sie ODER, UND oder NICHT. Aber wie macht man sie XOR? Es gibt keine einzige Erwähnung online.

$x\; \mathrm{XOR} \;y\; \mathrm{XOR} \;z = ((x|y)(\neg x|y)|z) (\neg ((x|y)(\neg x|y))|z)$ . Dies ist viel zu kompliziert und zeitaufwändig zum Zeichnen. Gibt es nicht einen anderen Weg?

Danke dass du dir die Zeit nimmst!

automata finite-automata closure-properties Xpl0
quelle

Hinweis: xor ist eine symmetrische Mengendifferenz .

Raphael

Danke Raphael! Was ich letztendlich tat, war ε-Schließung, aber einen Zustand als akzeptierend festzulegen, wenn die Anzahl der darin enthaltenen akzeptierenden Zustände ungerade war. Wenn ein Zustand keinen Übergang für ein Symbol hatte, habe ich nur die Ablehnung für diesen Zustand angenommen, aber nicht für die anderen, mit denen er gruppiert wurde.

Xpl0

Antworten:

Beachten Sie, dass die Konstruktion für den Schnittpunkt und die Vereinigung ("und" und "oder") zweier Automaten genau gleich ist, mit Ausnahme der Definition, welche Zustände akzeptieren. Das gleiche Prinzip gilt für jede boolesche Kombination einer endlichen Menge von Sprachen: Verwenden Sie die Produktkonstruktion und die entsprechende Definition, welche Zustände akzeptiert werden sollen.

David Richerby
quelle

Sehr hilfreich, alles machte sofort Sinn. Vielen Dank!

Xpl0

Da die drei Maschinen alle deterministisch sind, ist die kombinierte Operation überhaupt nicht kompliziert. Führen Sie die Maschinen parallel aus, wobei Sie eine direkte Produktkonstruktion verwenden, wie sie auch für die Kreuzung verwendet wird, und bei jedem XOR mit drei Zuständen das Vorhandensein von Endzuständen, um zu überprüfen, ob der neue Zustand für das XOR-Produkt akzeptiert werden soll.

Hendrik Jan.
quelle

Es gibt keinen großen Unterschied zwischen Ihrer Antwort und der von David, aber ich musste eine auswählen. Ich bin sehr dankbar für Ihre Hilfe!

Xpl0

Richtig: Unsere Antworten wurden innerhalb einer Minute voneinander geschrieben. Ich bin froh, dass wir helfen konnten. Ihr Dank ist mehr wert als die Credits, die hier auf dem Spiel stehen.

Hendrik

Da Sie nur mit DFAs arbeiten, können Sie zwei Automaten XOR-verknüpfen, indem Sie das Kreuzprodukt der beiden Automaten erstellen und dann die Zustandspaare als akzeptierende Zustände annehmen, von denen ein Zustand ein akzeptierender Zustand ist, jedoch nicht beide.

Beachten Sie, dass diese Konstruktion nur für DFAs funktioniert, bei denen jeder Status genau einen Nachfolgerstatus für jedes Alphabetsymbol hat. Dies stellt sicher, dass Sie bei der Simulation des Automaten immer einen Zustand erreichen und die Annahme eines Wortes nur davon abhängt, ob dieser Zustand ein Endzustand ist oder nicht. Manchmal werden DFAs so definiert, dass jeder Status höchstens einen Nachfolgerstatus für jedes Alphabetsymbol hat. In diesem Fall funktioniert die obige Konstruktion nicht mehr, da es jetzt einen zweiten Grund gibt, warum ein Wort nicht akzeptiert wird: Mit einigen Wörtern wird überhaupt kein Zustand erreicht.

Hoopje
quelle

"In diesem Fall funktioniert die obige Konstruktion nicht mehr" - im Grunde genommen. Fügen Sie einen Fehlerzustand ein und verwenden Sie die Standardkonstruktion oder übertragen Sie fehlende Übergänge (dh Zurückweisung) auf den Produktautomaten.

Raphael

@ Raphael. Natürlich können Sie einen Fehlerstatus hinzufügen. Auf diese Weise stellen Sie sicher, dass jeder Staat genau einen Nachfolgestaat hat, und dann werden die Bauarbeiten ausgeführt. Der Punkt ist, dass dies ein notwendiger Schritt ist.

Hoopje

Nein, ist es nicht. Die Konstruktion ist leicht anzupassen; Vielleicht war ich nicht klar genug? Wenn eine der beiden Komponentenautomaten keinen Übergang für den Buchstaben hat, gehen Sie so vor, als ob sie abgelehnt worden wäre (dh keinen Übergang für die Schnittmenge einschließen; einen für die Vereinigung und die symmetrische Mengendifferenz einschließen und zum entsprechenden ursprünglichen Automaten wechseln).

Raphael

Vielen Dank, Hoopje! Ich habe im Grunde Ihre Anweisungen befolgt, nur mit dem, was Raphael hinzugefügt hat.

Xpl0

@ Raphael. Dann müssen Sie wissen, welche Boolesche Funktion während der Erstellung der Zustände angewendet wird , und nicht nur, wenn Sie auswählen, welche Zustände akzeptiert werden (wie in allen Antworten auf die Frage angegeben).

Hoopje