Aufgabe zu Sprache

vip*r

Gegeben seien zwei endliche Automaten M1 und M2. Geben Sie eine Konstruktionsvorschrift an, um daraus einen Automaten M3 mit $L(M3) = L(M1) \cdot L(M2)$ zu gewinnen.

Demonstrieren Sie ihre Idee an der Sprache:

$L = \{ w \in \Sigma_{\text{Bool}}^{\star} | \text{w beginnt mit 00}\} \cdot \{ w \in \Sigma_{\text{Bool}}^{\star} | \text{Zahlwert(w)} \% 3 \}$

Ich darf hier mit NEA, DEA, oder $\epsilon$ -NEA konstruieren.

Ich hab nun zur linken Sprache gleich mal eine Frage. Ich hab dazu einen NEA konstruiert. Den sieht man hier: http://s7.directupload.net/file/d/2871/8y2ptvki_jpg.htm Ist hier der linke oder der rechte Automat richtig? Also meiner Meinung nach sollte der linke Automat stimmen, aber sicher bin ich mir leider nicht.

Eine weitere Frage: In der theoretischen Informatik bedeutet ja so ein $\cdot$ eigentlich immer die Konkatenation. Ich gehe mal davon aus, dass bei dieser Aufgabe auch die Konkatenation gemeint ist. Also muss ich, wenn ich beiden "Teilautomaten" entworfen habe, irgendwie die Sprachen der zwei Teilautomaten miteinander konkatenieren. Aber: Wie macht man das? Muss ich hier dann die zwei Teilautomaten miteinader schneiden? Ich hab gelesen, dass gilt: $L1 \cdot L2 = L1L2 = \{ vw | v\in L1 \wedge w \in L2 \}$

Was ist mit Konstruktionsvorschrift gemeint? Ich verstehe darunter einfach einen Automaten, wie ich in dem Bild gezeichnet hab der entsteht, wenn ich die beiden Teilautomaten geschnitten habe. Stimmt das?

Wenn ihr mir helfen würdet, wäre ich sehr dankbar!

daki

was hältst du davon das Zeug mal mit deinen Komilitonen oder in den Übungen bzw. Tutorien zu besprechen? Bzw. generell dich mal in das Fach einzuarbeiten und zu erlernen welche Aufgabentypen man mit welchen Automatentypus erschlagen kann.

Die ganzen Aufgaben die du hier postest sind stellenweise nah an trivial.

Deine Erklärung ist im übrigen falsch, hier wird ein Produktautomat gesucht, den auch erklärst, eine Konkatenation ist was völlig anderes.

vip*r

Bedeutet also der $\cdot$ Produktautomat?

Tja, wenn ich aber keine Möglichkeit habe, das mit Kollegen zu besprechen, da es keiner (mehr) machen muss? Dann beiß ich ins Gras, oder wie?

Welcher der beiden Automaten war denn nun der richtige?

daki

meines erachtens beide falsch.

der erste akzeptiert wörte mit 01 beginnend, der zweite akzeptiert wörter mit 1^* beginnend

Bashar

daki schrieb:

Deine Erklärung ist im übrigen falsch, hier wird ein Produktautomat gesucht

Sicher? Die Aufgabe verlangt, eine allgemeine Vorschrift anzugeben ... das heißt, man soll in einer Übungsaufgabe mal eben den Produktautomaten erfinden. Das wäre eine ziemlich heftige Aufgabe, normalerweise wird diese Operation in der Vorlesung vorgestellt. Konkatenation finde ich realistischer, da muss man ja nur die Automaten (NEA) zusammenkleben. Das Produkt wird auch IMO normalerweise mit $\times$ notiert.

edit: Achtung, Produkt von Sprachen scheint dasselbe wie Konkatenation von Sprachen zu sein; aber ein Produktautomat erkennt den Schnitt von Sprachen.

daki

ok - ich hätte das einfach auf nen Tippfehler zurückverfolgt.

Dennoch stimmen die beiden Lösungsmöglichkeiten dann aber nicht.

Für die Konkatenation musste dann einfach die Automaten aneinander hängen. FS des einen ist SS des DEA.

vip*r

Bashar schrieb:

Sicher? Die Aufgabe verlangt, eine allgemeine Vorschrift anzugeben ... das heißt, man soll in einer Übungsaufgabe mal eben den Produktautomaten erfinden. Das wäre eine ziemlich heftige Aufgabe, normalerweise wird diese Operation in der Vorlesung vorgestellt. Konkatenation finde ich realistischer, da muss man ja nur die Automaten (NEA) zusammenkleben. Das Produkt wird auch IMO normalerweise mit $\times$ notiert.

edit: Achtung, Produkt von Sprachen scheint dasselbe wie Konkatenation von Sprachen zu sein; aber ein Produktautomat erkennt den Schnitt von Sprachen.

Ich hab jetzt in diesem Bild die beiden Automaten nochmal neu gemacht. Bild: http://s7.directupload.net/file/d/2875/x6ll3phq_jpg.htm

Ich hoff, die stimmen jetzt. Soll der Punkt nun "Konkatenation" oder "Produktautomat" bedeuten? Die Konkatenation wurde schon eingeführt und darf als gegeben hingenommen werden. Was verstehst du unter "zusammenkleben"? Du schreibst auch, dass die Konkatenation von zwei Automaten gleich dem Produktautomaten ist, nur mit dem Unterschied, dass im Produktautomaten die Schnittmenge der akzeptierenden Zustände gekennzeichnet wird.

Muss ich also für die Konkatenation der beiden Automaten mit der Potenzmengenkonstruktion arbeiten?

daki schrieb:

ok - ich hätte das einfach auf nen Tippfehler zurückverfolgt.

Dennoch stimmen die beiden Lösungsmöglichkeiten dann aber nicht.

Für die Konkatenation musste dann einfach die Automaten aneinander hängen. FS des einen ist SS des DEA.

Bezeichnest du den finite state mit FS? Was soll SS heißen?

Mein Tipp: Startzustand (start state)

daki

SS Start state

anderen haste richtig erkannt,

ne Konkatenation und Produktautomat sind völlig verschiedene Sachen.

Konka. Wenn der 1. Automat akzeptiert ist der 2. Automat an der Reihe.

Produktautomat: Akzeptiert wenn beide gleichzeitig akzeptieren - wird daher auch völlig anders konstruiert.

Was nun da genau gefordert ist weiß ich nicht - wie schon gesagt wurde, kommt es darauf an wie das * bzw. der Punkt definiert ist. Nach meiner Auslegung wäre es der Produktautomat, nach Bashars der Konkatenierte.

vip*r

daki, danke für deine Antwort.

Ich gehe mal davon aus, dass hier der Produktautomat gemeint ist. Da würde man ja dann die zwei Teilautomaten mit der Potenzmengenkonstruktion zu einem einzigen Automate zusammenfassen und dann noch die akzeptierenden Zustände beider Teilautomaten schneiden, welche im Produktautomaten dann akzeptierend werden.

Kann mir vielleicht jemand sagen, ob die zwei Teilautomaten nun richtig sind? Vor allem interessieren würde mich der Automate M1. Bei M2 der modulo3-Automat bin ich mir sehr sicher, dass er richtig ist.

Bashar

vip@r schrieb:

Ich hoff, die stimmen jetzt. Soll der Punkt nun "Konkatenation" oder "Produktautomat" bedeuten?

Mit Sicherheit nicht "Produktautomat", weil da zwei Sprachen und nicht zwei Automaten verknüpft werden. Der Produktautomat erkennt den Schnitt von zwei Sprachen, das würde man dann auch als Schnitt notieren.

Was verstehst du unter "zusammenkleben"?

Denk bitte selbst mal kurz drüber nach.

Du schreibst auch, dass die Konkatenation von zwei Automaten gleich dem Produktautomaten ist

Hä, was, wie bitte? Ich schreib extra noch, dass man aufpassen muss, das Produkt von Sprachen nicht mit dem Produkt von Automaten zu verwechseln. Es ist lediglich BEI DIESEM BEISPIEL zufällig dasselbe.

Muss ich also für die Konkatenation der beiden Automaten mit der Potenzmengenkonstruktion arbeiten?

Nein.

vip*r

Stimmen denn nun die zwei Automaten die ich nochmal als neues Bild hochgeladen habe?

Bashar schrieb:

Denk bitte selbst mal kurz drüber nach.

Ich verstehe unter zusammenkleben (ich hab ehrlich gesagt "zusammenkleben" bei so Sprachentheorie noch nie gehört), dass der Endzustand des ersten Automaten mit dem Anfangszustand des zweiten Automaten verbunden wird.