Formale Sprachen #21 - Produktautomat
Вставка
- Опубліковано 25 жов 2014
- Wir konstruieren den Produktautomaten, um zu zeigen, dass der Schnitt von zwei erkennbaren Sprachen erkennbar ist.
KORREKTUR (Version 2):
Im Video beschreibe ich die Sprache, die der obere Automat erkennt, falsch. Man kann sie wie folgt beschreiben: Es sind alle Wörter, die ein Suffix der Form a(ab)* haben, also sie enden auf eines der Wörter a, aab, aabab, aababab, ...
Super Video! Hat mir bei meinen Unihausaufgaben sehr weitergeholfen. Tolle, anschauliche Darstellung, wie sich ein Produktautomat aus zwei DFAs zusammensetzt! :)
Vielen Dank, das hat mir weitergeholfen.
Klasse Video :) ist also ein Produktautomat die Schnittmenge 2 DEAs ? Wenn ja wie macht man das mit den Automaten die zusätzlich noch Müllzustände besitzen? Also die eine Totale Übergangsfunktion besitzen
Hallo, erst mal vielen Danke für die tollen Videos. Ich habe noch eine Frage hierzu. Gibt es eine Möglichkeit einen Differenz Automat zu konstruieren? Also Sprache A ohne Sprache B? Ich weiß das man diesen durch "scharfes Hinsehen" also durch überlegen konstruieren kann, da reguläre Sprachen unter der Differenz abgeschossen sind aber gibt es dafür ein Algorithmus?
Dominik Wagner Ja, auch die Differenz kann man mit einer Variante des Produktautomaten bekommen, indem man die Endzustände entsprechend wählt. Sind A und B unsere ursprünglichen Automaten, so wollen wir L(A) \ L(B), also "L(A) ohne L(B)" bekommen. Das sind die Worte, die von A erkannt werden, aber nicht von B. Also wählen wir dann im Produktautomaten die Zustände als Endzustände, bei denen die A-Komponente ein Endzustand ist, aber die B-Komponente kein Endzustand ist.Zum Beispiel im Video: Wählt man die Endzustandsmenge {A2,A3}, so bekommt man die Worte, die der obere Automat akzeptiert, aber der linke nicht. Wählt man stattdessen nur {B1} als Endzustandsmenge, dann bekommt man die Worte, die der linke Automat akzeptiert, aber der obere nicht.
Ein kleiner Hinweis, du sagst in 1:20 das der obere DEA Wörter erkennt bei denen unter den letzten beiden Symbolen min. ein a ist. Für ab endet der Automat im Zustand 1 und erkennt damit das Wort nicht. Aber der Zweck des Videos ist ein anderer, vielen Dank! Sehr hilfreich!
Ja, siehe Videobeschreibung!
Bist du hier noch aktiv? Wollte mal fragen, wie das aussieht, wenn vom Zustand A als Beispiel eine Kante mit a zu B führt, allerdings keine a Kante für 1 existiert? Wie würde man in diesem Fall für den neuen Zustand A1 vorgehen?
In dem Fall hätte A1 keine ausgehende a-Kante.
Danke für die Antwort auch wenn die Kommentare plötzlich weg sind ;)
1:30 ist nicht ganz richtig: obwohl das Wort ab ein a enthält, wird es nicht akzeptiert
Richtig! Siehe Videobeschreibung!
Könnte man nicht auch die Übergänge definieren, wo am einen Automaten ein a eingelesen wird und am anderen ein b? Warum hast du diese Übergänge nicht definiert?
Juls Right Wir wollen mit dem Produktautomaten beide das Durchlaufen beider Automaten gleichzeitig simulieren. Wenn wir also ein a mit dem Produktautomaten lesen, dann folgen wir den a-Kanten in beiden Ursprungsautomaten. Weshalb sollten wir eine Kante dort zeichnen, wo im einen Automaten ein a und im anderen ein b ist? Und mit was sollten wir diese Kante im Produktautomaten beschriften? Vielleicht habe ich die Frage auch nicht ganz verstanden.
Ok, ja das klingt dann natürlich logisch. Also zur Erklärung, ich schreibe in der nächsten Woche eine Klausur über Automatentheorie und im Skript ist der Übergang vom Produktautomaten definiert ( d für Übergangsfkt. )
( d1(z1,x1), d2(z2,x2)) --> deshalb dachte ich, dass x1 und x2 als EIngaben ja unterschiedlich sein können :)
Aber so reicht mir das dann schon , danke
Juls Right Alles klar. Ja also am Besten versteht man die Übergänge wohl, wenn man sich an einem Beispiel klar macht, dass der Produktautomat wirklich den Schnitt akzeptiert. Viel Erfolg noch!
Korrektur in der Beschreibung ist auch falsch? z.B. wird aa erkannt
Das Wort "aa" wird durch die Beschreibung abgedeckt, denn es hat "a" als Suffix.
Ich hab nichts gesehen, dass da Suffix steht.. upsi
AABAB wird auch erkannt
und was ist daran schlimm? das soll es ja auch, es erfüllt beide bedingungen (ungerade anzahl a's und in den letzten beiden buchstaben ist mind. ein a vorhanden