Schnittmenge zweier Automaten?
-
Hi Leute!
Nochmal eine Frage:
Ich hab zwei Automaten gegeben und möchte nun die Schnittmenge der beiden konstruieren. Wir haben dazu in der Vorlesung ein Schmea kennengelernt, aber leider jetzt daheim, weiß ich nicht mehr wie das gegangen ist, da auch zusätzlich die Folien nicht sehr viel dazu hergeben! Wisst ihr wie das geht?
Hier die beiden Automaten: http://imageshack.us/photo/my-images/864/67446530.jpg/
-
Du mußt quasi beide Automaten parallel mit der selben Eingabe arbeiten lassen. D.h. du mußt alle Kombinationen aus Zuständen beider Automaten bilden und die gleichartigen Kanten entsprechend übernehmen.
z.B. wird aus den 0-Kanten q0->q1 und A->B eine Kante (q0,A)->(q1,B).
(akzeptierende Zustände sind die Kombinationen der Endzustände der gegebenen Automaten, hier also (q2,A))
-
Versteh ich das richtig: Im Schnittmengenautomat wird's nur akzept. wenn beide elemente des "Mengenzustands" akzept. waren, oder?
-
Klar, ein Wort liegt ja auch nur in der Schnittmenge, wenn es in beiden gegebenen Mengen liegt.
-
Wenn ich mich jetzt im Zustand {q2, A} befinden und von dort aus nun mit 1 weitergehen möchte, dann komm ich von q2 aus nicht mehr weiter, von A aus aber auf B. Was mache ich in so einem Fall? Einen neuen Zustands DS (= dead state)?
Halt stop zurück: ich komm mit 1 weiter auf q0...
