Ist das hier Konkatenation eine von zwei Sprachen?

Neue Frage »

Auf diesen Beitrag antworten »
bandchef Ist das hier Konkatenation eine von zwei Sprachen?

Aufgabe:

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

Demonstrieren Sie Ihre Idee an der Sprache:
[latex]L = \{ w \in \Sigma_{\text{Bool}}^{\star} | \text{w beginnt mit 00}\} \cdot \{ w \in \Sigma_{\text{Bool}}^{\star} | \text{Zahlwert(w) mod 3} = 0 \}[/latex]

Hinweis: da hier nur allgemein von einem Automaten gesprochen wird, dürfen Sie nach Ihrer Wahl einen DEA, einen NEA oder einen [latex]\epsilon-NEA[/latex] konstruieren.



Hi Leute!

Zur obigen Aufgabe hab ich mir natürlich schon Gedanken gemacht. Ich hab für die Sprache M1 bzw. M2 schon Automaten entworfen. Diese sieht man in diesem Link: Bild.

So, nun steht zwischen den beiden Sprachen in der Aufgabenstellung ein Malpunkt. Laut meinen Folien ist das die Konkatenation von zwei Sprachen bzw. Automaten. Aber wie geht das? ODER: Ist mit diesem Malpunkt der Produktautomat gemeint?
 
Auf diesen Beitrag antworten »
Karlito

Hallo bandchef,

als erstes ein Hinweis: Bitte keine Bilder verlinken, besser anhängen, da die Links gern verloren gehen. Deshalb im Anhang noch einmal dein Bild.

Ich gehe auch davon aus, dass es sich hier um die Konkatenation handelt. Der Produktautomat wird m.E mit einem Kreuz gekennzeichnet, also [latex] L(M1) \times L(M2)[/latex].

Dann sind deine Automaten falsch! Der erste realisiert 00 ist Infix von w. Beispielsweise ist das Wort 100 möglich.

Beim zweiten nehme ich an, dass es keine führenden 0 geben darf oder die 0 steht allein. Der Automat M2 leistet das nicht. Z. B. ist das Wort 000 enthalten und die 1 allein wird nicht erkannt.

Für die Konstruktion eines Automaten, welcher die Konkatenation der Wörter der gegebenen Automaten akzeptiert, musst die die beiden Automaten hintereinanderhängen. Mach mal einen Vorschlag wie das ablaufen könnte.

VG,

Karlito
Auf diesen Beitrag antworten »
bandchef

Danke, Karlito!

Das mit den verlinkten Bildern werd ich mir für die Zukunft merken!

Hm, dass die zwei Automaten falsch sind, hab ich jetzt nicht gedacht. Ich werd's nochmal neu versuchen.



Zitat:
Der Automat M2 leistet das nicht. Z. B. ist das Wort 000 enthalten und die 1 allein wird nicht erkannt.

Nehmen wir mal an es kommt der dezimale Zahlwert 1 des Wortes w. Zahlwert(w) repräsentiert dies ja, dann muss ich 1 % 3 = 1 rechnen. Dies ist aber nicht gleich 0 als darf der Automate nicht akzeptiere, was er auch nicht tut. Wenn nur eine einzige 1 kommt, bleibt der Automat beim nicht akzeptierenden Zustand P1 stehen!


Zitat:
Beim zweiten nehme ich an, dass es keine führenden 0 geben darf oder die 0 steht allein.

Hm, das finde ich bei dieser Aufgabe übrigens auch sehr schlecht formuliert. Woher soll ich wissen, ob führende Nullen nicht erlaubt sind? Wie man diesen Automaten allerdings realisieren soll, damit er führende Nullen nicht akzeptiert, weiß ich nicht. Aber: Wenn eine dezimale Null kommt, dann kommt es ja immer drauf an wie viel Bits zur Darstellung dieser dezimalen Zahl verwendet werden. Somit MUSS dieser Automate eigentlich führende Nullen akzeptieren, oder bin ich da jetzt komplett falsch gewickelt? Ich verstehe das so (ich verwende jetzt einfach für Demo-Zwecke eine 8-Bit-Zahl): [latex]0_{10} = 00000000_2[/latex] oder [latex]3_{10} = 00000011_2[/latex]



[latex]L_1 = \{ w \in \Sigma^{\star}_{\text{Bool}} | w \text{ beginnt mit 00} \}[/latex]

[latex]L_2 = \{ w \in \Sigma^{\star}_{\text{Bool}} | \text{Zahlwert(w) mod 3} = 0\}[/latex]



Da es ja in der Aufgabenstellung heißt man darf auch epsilon-NEAs bauen, ist mein Vorschlag für die Konkatenation der beiden Automaten folgender:



EDIT: Wie kann man in diesem Forum, Bilder so schön unter Textblöcken anordnen, wie du es in deinem ersten Beitrag hier gemacht hast? Ich hab das leider nicht herausgefunden :-(
Auf diesen Beitrag antworten »
Karlito

Bei mir ist von der Definiton von L(M2) war bei mir komsicherweise nur unvollständig angekommen:

[latex]L_2 = \{ w \in \Sigma^{\star}_{\text{Bool}} | \text{Zahlwert(w) }[/latex]

deshalb die Antwort...

Wie man alle Zahlen, die durch 3 Teilbar sind durch einen endlichen Automaten erkennt weis ich leider nicht... Da müsste ich ein wenig darüber nachdenken.

Aber die Verknüpfung der beiden Automaten stimmt leider auch nicht. Du würdest so ein Wort erkennen, welches entweder aus der einen oder aus der anderen Sprache ist. DIe Konkatenation ist ein wenig anders... Es muss erst durch den einen und dann durch den anderen Automaten erkannt werden. Überlege auch welche Konsequenz sich dann für den Finalzustand der ersten Sprache ergibt... Du musst den Automaten ein wenig anpassen...

VG,

Karlito
 
Auf diesen Beitrag antworten »
bandchef

Ich hab mir dann zur Konkatenation nochmals Gedanken gemacht und dabei auf den Automaten hier gekommen.

Zitat:
Original von Karlito
Überlege auch welche Konsequenz sich dann für den Finalzustand der ersten Sprache ergibt...


Ich verstehe jetzt in der Tat nicht so genau, was das jetzt mit den Finalzuständen auf sich hat. Kannst du vielleicht näher drauf eingehen?
Auf diesen Beitrag antworten »
HueHang

Die [latex]\varepsilon[/latex] Transition sieht schonmal gut aus und der gesamte Automat sieht auch gut aus :p
Auf diesen Beitrag antworten »
Karlito

Ich meinte, dass die Finalzustände des ersten Automaten natürlich keine mehr sein dürfen. Hast du ja richtig gelöst.

VG,

Karlito
Auf diesen Beitrag antworten »
bandchef

Danke für die Rückantwort! Gefällt mir diese Forum!
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »