3. Frage zu den Abschlusseigenschaften

Frage zu den Abschlusseigenschaften

  • V

    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?)

    0
  • C

    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.

    0
  • S

    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.

    0
  • V

    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?

    0
  • C

    Grundlagen Mengenleere: L1 - L2 == L1 ∩ -L2. Das heißt, du kannst den Automaten mittels Schnittmenge und Komplement bilden.

    0
  • V

    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?

    0
  • C

    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.

    0
  • V

    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.

    0
  • C

    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 😃

    0
  • V

    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}

    0
Anmelden zum Antworten