Frage zu den Abschlusseigenschaften
-
Hi Leute!
Wenn ich zwei Sprachen habe z.B. L1 und L3 von denen zusätzlich den Automaten gegeben habe und es weiter heißt geben sie den Automaten L4 = L1 ∪ L3 und L5 = L1 ∩ L3 an, dann haben wir gelernt, dass man L4 bzw. L5 durch einen sogenannten Produktautomaten erreichen kann. Die Frage die sich mir jetzt stellt, ist, wie ich den unterschied zwischen Vereinigung und Schnittmenge der beiden Sprachen aus dem Produktautomaten rausziehe...
Versteht ihr was ich meine?
-
Erstens: Vielleicht solltest du dazusagen, daß du von regulären Sprachen und endlichen Automaten redest.
Zweitens: Der Unterschied besteht darin, wie du die akzeptierenden Zustände des Produkt-Automaten auswählst. Für den Durchschnitt nimmst du die Zustände, bei denen beide Teile akzeptieren, für die Vereinigung alle, bei denen ein Teil akzeptiert.
PS: Was ist eigentlich aus L2 geworden
-
Was ist eigentlich aus L2 geworden
Hm...; das ist wohl eine der schwierigsten Frage, die ich dir jetzt SO EINFACH überhaupt nicht erklären kann
Ich rekapituliere:
- Für die Schnittmenge der beiden Automaten müssen beide Teile der eu entstandenen Zustände sich in einem akzept. Zustand der ursprünglichen Automaten befinden.- Für die Vereinigung reicht es, wenn einer der beiden Teile der Zustände des neu entstandenen Automaten akzept. ist. (Die Vereinigung beinhaltet aber dann nicht auch die Zustände, die die Schnittmenge enthält, oder?)
-
vip@r schrieb:
- Für die Vereinigung reicht es, wenn einer der beiden Teile der Zustände des neu entstandenen Automaten akzept. ist. (Die Vereinigung beinhaltet aber dann nicht auch die Zustände, die die Schnittmenge enthält, oder?)
Ich präzisiere meine letzte Aussage: mindestens ein Teil - da sind natürlich auch die Endzustände des Schnittmengen-Automaten enthalten.
-
Wobei ein Automat für die Vereinigung natürlich noch viel einfacher zu konstruieren ist als über den Produktautomaten: Beide Automaten nebeneinander malen, neuen Startzustand dazu, Epsilon-Kanten vom neuen Startzustand zu den alten Startzuständen, fertig.
-
SG1 schrieb:
Epsilon-Kanten
Da ich hier DEA's konstruieren soll, wird mich das nicht weiter bringen
Wenn ich nun z.B. die fiktive Sprache L = L1-L2 berechnen soll, wie sieht dass dann mit den Zuständen aus? Mathematisch würde es ja bedeuten, dass nur die alleinigen akzept. Zustände der Sprache L1 markiert werden müssen, oder? Anders gesagt, es dürfen nur die entstandenen neuen Zustände markiert werden, in denen nur der Teil der Sprache L1 akzept. ist. Stimmt das so?
-
Grundlagen Mengenleere: L1 - L2 == L1 ∩ -L2. Das heißt, du kannst den Automaten mittels Schnittmenge und Komplement bilden.
-
Q1={A,B,C}
Q2={D,E}Das sind die Mengen der Zustände von L1 und L2. Die unterstrichenen Elemente sind die akzept. Zustände.
Vereinigung: Q1 υ Q2 = {{A,D},{B,D},{C,D},{C,E}}
Schnitt: Q1 ∩ Q2 = {C,D}
Differenz: Q1-Q2={}Stimmt das so?
-
Nein, der letzte Teil stimmt nicht. Wie bildest du denn den Automaten für das Komplement einer regulären Sprache?
PS: Die gesamten Zustände (und Übergänge) sollten für alle drei Automaten identisch sein. Und abgesehen von nicht-erreichbaren Zuständen solltest du auf insgesamt 6 Zustände kommen.
-
Nein, der letzte Teil stimmt nicht.
Ich denke mal dass du damit die Differenz meinst, oder?
Meinst du so:
{A,B,C} ∩ {D,E}
PS: Die gesamten Zustände (und Übergänge) sollten für alle drei Automaten identisch sein.
Das hab ich nicht so ganz verstanden.
-
vip@r schrieb:
PS: Die gesamten Zustände (und Übergänge) sollten für alle drei Automaten identisch sein.
Das hab ich nicht so ganz verstanden.
Das heißt, daß du bei der Kreuzprodukt-Konstruktion für alle drei Fälle das selbe Verfahren verwendest - also kommt auch der selbe Produkt-Automat heraus (abgesehen von der Auswahl der akzeptierenden Zustände).
Aber vermutlich war das einfach nur eine Kritik an deiner ungenauen Ausdrucksweise
-
vip@r schrieb:
Meinst du so:
{A,B,C} ∩ {D,E}
Stimmt das nun so?
Wenn ja, dann würde ja als akzept. Zustand des neuen Automate {C,E} rauskommen.
Nochmal für alle 3 "neuen" Automaten:
Vereinigung: Q1 υ Q2 = {{A,D},{B,D},{C,D},{C,E}}
Schnitt: Q1 ∩ Q2 = {C,D}
Differenz: Q1 - Q2 = {C,E}