Kreuzprodukt unvollständiger DFAs

Question

Ich versuche, ein Kreuzprodukt zwischen zwei DFAs zu machen, aber beide sind unvollständige DFAs.

Das folgende Bild ist die Antwort, die ich für den Schnittpunkt des Kreuzprodukts zwischen zwei unvollständigen DFAs gefunden habe. Das Alphabet ist {a, b, c, d, e}.

Ist es richtig, oder wie die Tatsache, dass sie alles unvollständig ändern sind?

Answer 1

Die Tatsache, dass sie unvollständig sind, macht Ihre Arbeit anders, wenn Sie das Kreuzprodukt konstruieren, um die Vereinigung zu finden; Für die Kreuzung können Sie diesen grundlegenden Ansatz jedoch noch verwenden. Aber Sie einige Fehler gemacht:

Lassen Sie uns in der oberen linken beginnen, und schauen Sie sich alle Übergänge aus dem Zustand A1:

Zuerst müssen Sie ein Zustandsübergang c vom Zustand der Bezeichnung A1A2 angeben. Dies ist jedoch nicht korrekt, da im oberen DFA, der mit c gekennzeichnet ist, kein Übergang von A zu A stattfindet. Dann haben Sie einen Übergang mit der Bezeichnung a, der vom Zustand A1 zu sich selbst geht. Dies ist auch falsch, da es keinen Übergang vom Status 1 zu einem beliebigen mit a gekennzeichneten Objekt gibt. Ebenso gibt es keinen Übergang aus dem Status 1 mit der Bezeichnung b, so dass auch Ihr Übergang von A1 zu B1 ungültig wird.

Wenn mit unvollständigen DFAs und machen einen Quer Produkt wie dieses arbeitet, werden Sie nur abgehende Kanten (p,q) für einen Staat haben, wenn ein Brief da ist, dass sowohl staatliche p und Zustand q für abgehende Kanten aufweisen.

Daher gibt es keine Übergänge aus dem Startzustand. An diesem Punkt können wir aufhören zu arbeiten, da es keine Übergänge mehr aus dem Startzustand gibt, gibt es keinen Punkt - der resultierende DFA entspricht nichts.

Eine andere Möglichkeit, wie man das angehen kann, besteht darin, zuerst beide DFAs durch Hinzufügen eines nichtakzeptierenden Zustands zu vervollständigen (ich nenne diesen Zustand ∅). Dieser Zustand sollte von jedem Zustand für jeden Buchstaben, für den es nicht bereits eine andere abgehende Kante gibt, eine Kante haben. Zum Beispiel würde es in der ersten DFA eine Kante von A bis ∅ für c, d und e geben. Außerdem sollte eine Kante von ∅ bis ∅ für jeden Buchstaben vorhanden sein. Jetzt sind beide DFAs abgeschlossen.

Wenn Sie das tun, Sie am Ende mit Kanten aus A1 gehen: A∅ für a, B∅ für b, ∅1 für c und ∅∅ für d und e. Der Rest bleibt als Übung übrig, aber wenn Sie es vollständig zeichnen, werden Sie wieder feststellen, dass es keinen Pfad von A1 zu einem akzeptierenden Zustand gibt.

Die Erstellung von DFAs ist in der Tat genau das, was Sie tun müssen, wenn Sie das Kreuzprodukt erstellen, um die Union zu finden - mit der Schnittmenge ist es einfach möglich, alle ∅ in DFA seit dem Erreichen von ∅ wegzuwerfen bedeutet, dass Sie nie einen akzeptierenden Zustand erreichen werden, aber mit der Gewerkschaft müssen Sie sie behalten, weil einige Staaten, die ∅ mit einbeziehen, Zustände des Kreuzprodukts annehmen können. (Sie können immer noch den Status ∅∅ und jede Kante zu diesem wegwerfen)