Ist dieser Schnittpunkt von DFAs korrekt?

Ich bin eine Konstruktion deterministischen endlichen Automaten für eine Sprache aller Strings (DFA) definiert über , deren Länge auch für die Anzahl der s ungerade ist . Ich habe jedes DFA separat erstellt und dann kombiniert: $\{0,1\}$ $1$

dfas und ihre Vereinigung

Ist das angegebene Verfahren zum Kombinieren von DFAs korrekt?
EDIT: Ursprünglich schrieb Union; tatsächlich die Kreuzung nehmen.
Würde jemand Material zum Erstellen von DFAs vorschlagen,
wenn die Länge und Anzahl von s oder s begrenzt sind? $0$ $1$

Laut Link von Merbs habe ich diesen FA entwickelt. Geben Sie hier die Bildbeschreibung ein
Dieser FA akzeptiert keine Sprache gleicher Länge.

automata regular-languages finite-automata Rafay Zia Mir
quelle

Ihr Ansatz scheint korrekt zu sein, aber Sie sollten den Schnittpunkt und nicht die Vereinigung der beiden DFAs verwenden.

A.Schulz

Ich habe nur 3 Methoden gelernt, wie die Vereinigung von FAs, die Verkettung von FAs und das Schließen von FAs. Ich suche, kann aber den Schnittpunkt von FAs nicht finden. Können Sie mich auf einen nützlichen Link verweisen?

Rafay Zia Mir

Aus einer Google-Suche: Diese Website ist gut, aber das Wesentliche ist, dass Sie den Schnittpunkt der akzeptierenden Zustände nehmen.

Merbs

Ich habe diesen Link besucht, aber dies ist ein spezifisches Beispiel, keine Regel. Wenn wir auf eine schwierige FA stoßen, ist es schwierig, eine Kreuzung zu konstruieren.

Rafay Zia Mir

Gegeben seien zwei DFAs mit und Zuständen, die Konstruktion eines mit DFA Zuständen (mit jedem Zustand ein Paar von Zuständen in den ursprünglichen DFAs darstellt) wird die Regel; und dann können Sie den resultierenden DFA durch eine Reihe von (meist heuristischen?) Prozeduren minimieren.

m

$m$

n

$n$

m n

$mn$

Merbs

Antworten:

Ja, dies wird als Produktkonstruktion bezeichnet. Wenn die DFAs und , können wir konstruieren : $M_1$ $M_2$ $M=M_1\times M_2$

$M$ besteht aus Zustandspaaren aus seinen konstituierenden DFAs. Wenn also die ursprünglichen DFAs die Zustände und , wäre das Produkt . $A,B,C$ $x,y,z$ $\{Ax,Ay,Az,Bx,By,Bz,Cx,Cy,Cz\}$
Die Übergangsfunktion wird so aktualisiert, dass, wenn in einem bestimmten Schritt eine Zeichenfolge dazu führen würde, dass von Zustand nach und von nach , das Produkt von nach $M_1$ $A$ $B$ $M_2$ $x$ $y$ $Ax$ $By$
Der Anfangszustand ist das Paar, das aus den Anfangszuständen der konstituierenden DFAs (dh ) besteht. $Ax$
Wenn wir den DFA konstruieren, der bestimmt, ob beide konstituierenden DFAs die Zeichenfolge akzeptieren würden, dann sind die Akzeptanzzustände von der Schnittpunkt (diese Paare, die aus Akzeptanzzuständen von beiden bestehen). Wenn wir die DFA konstruieren , die feststellt , ob entweder DFAs der beiden konstituierenden würde die Zeichenfolge akzeptieren, dann akzeptieren die Zustände von die ist Vereinigung (die Paare , bestehend aus akzeptieren Staaten von entweder). In Ihrem Beispiel sind und die Akzeptanzzustände von und . Die Kreuzung wäre $M$
$M$
$x_1$ $y_0$ $M_1$ $M_2$ $\{x_1y_0\}$ während die Vereinigung . $\{x_1y_0,x_1y_1,x_0y_0\}$

Ich habe einige andere DFAs bezüglich Längenbeschränkungen als Referenz beigefügt.

Beispiel dfas

Merbs
quelle

in Fällen der Vereinigung die Menge der akzeptierenden Zustände nicht ? (Nicht dass irgendjemand diese Konstruktion für die Vereinigung verwenden würde; in diesen Fällen genügen Zustände im Gegensatz zu diese Konstruktion ergibt. Zumindest wenn wir über NFA sprechen.)

M_{1} Q_{2} \cup Q_{1} M_{2}

$M_1Q_2 \cup Q_1M_2$

| Q_{1} | + | Q_{2} | + 1

$|Q_1|+|Q_2|+1$

| Q_{1} | | Q_{2} |

$|Q_1||Q_2|$

Raphael

@ Raphael, Ihr Kommentar war zwar korrekt, aber so kompliziert, dass ich ihn nicht ohne weitere Überlegungen verstand, also habe ich versucht, ihn zu "laienhaft" zu machen. Wenn Sie meine Antwort bearbeiten möchten, um eine Diskussion über NFAs aufzunehmen, können Sie sie zu einem Community-Wiki machen (oder Ihre eigene Antwort hinzufügen).

Merbs

@Merbs, danke für deine Hilfe und Antwort. Entschuldigung für die späte Antwort, aber ich habe diese Methode bei anderen FAs ausprobiert und dies war erfolgreich.

Rafay Zia Mir

OK, ein bisschen "laienhaft". Nehmen Sie die DFAs und . Betrachten Sie den DFA , wobei definiert ist durch: Die Idee ist, dass der Zustand von die Zustände aufzeichnet, in denen und wären, wenn sie den String separat verarbeiten würden. akzeptiert nur, wenn beide dies tun. $M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ $M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)$ $M = (Q_1 \times Q_2, \Sigma, \delta, (q_1, q_2), F_1 \times F_2)$ $\delta$

δ ((q^{'}, q^{″}), a) = (δ_{1} (q^{'}, a), δ_{2} (q^{″}, a))

$\delta((q', q''), a) = (\delta_1(q', a), \delta_2(q'', a))$

M

$M$

M_{1}

$M_1$

M_{2}

$M_2$

M

$M$

vonbrand
quelle

Ich bin mir nicht sicher, auf welche Weise dies "laienhaft" ist. Dies ist die (richtige) formale Definition für die Produktkonstruktion. Sie sollten erwähnen, wie die Zustandsmenge von in vielen Fällen reduziert werden kann; niemand will den ganzen Mist zeichnen.

M

$M$

Raphael