Frage zu Übung 2.3a(3.)

Julius
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 237
Registriert: 5. Okt 2005 15:52

Frage zu Übung 2.3a(3.)

Beitrag von Julius »

Kann mir jemand erklären was der hintere Teil des omega-regulären Ausdrucks sicherstellen soll und warum wir diesen brauchen?


\(L(B_1)=\left\{(\left\{ab,ab*bb\right\})^{\omega},(\left\{ab,ab*bb\right\})*ab^{\omega}\right\}\)


Edit: Vielleicht könnte auch jemand mal das prinzipielle Vorgehen zum Finden dieser Sprache erklären.

amittelbach
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 1. Feb 2007 20:07

Beitrag von amittelbach »

Ich würde behaupten, der zweite Ausdruck ist durchaus Teil der Sprache des Automaten. Diese wird aber meiner Ansicht nach bereits vollständig durch den ersten Ausdruck beschrieben.

\(ab^\omega\) heißt denke ich einfach es kommt ein a und dann nur noch bs. Das wäre der weg q0q2q2q2q2...

Tillmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Re: Frage zu Übung 2.3a(3.)

Beitrag von Tillmann »

Julius hat geschrieben:\(L(B_1)=\left\{(\left\{ab,ab^*bb\right\})^{\omega},(\left\{ab,ab^*bb\right\})^*ab^{\omega}\right\}\)
Wir haben eine Alternative auf oberste Ebene, wir können also zunächst die beiden Teilausdrücke einzeln betrachten, und dann später die Vereinigungsmenge der beschriebenen Sprachen bilden.

Der erste Teilausdruck
  • \((\left\{ab,ab^*bb\right\})^{\omega}\)
beschreibt unendlich lange Wörter, die abwechselnd ein a und mindestens ein b enthalten. "Mindestens ein b" ist dabei unnötig kompliziert ausgedrückt als "entweder ein oder mindestens zwei b". Eine einfachere Darstellung derselben Sprache wäre also
  • \((\left\{abb^*\right\})^{\omega}\)
Nicht erlaubt sind jedenfalls Wörter, die am Ende nur noch b's und kein a mehr enthalten.

Der zweite Teilausdruck
  • \((\left\{ab,ab^*bb\right\})^*ab^{\omega}\)
beschreibt unendliche lange Wörter, deren endlicher Anfang dieselbe Struktur hat, wie sie der erste Teilausdruck beschreibt, also abwechselnd a's und Gruppen von mindestens einem b. Ab irgendeinem a kommen dann aber nur noch b's. Auch dieser Teilausdruck läßt sich natürlich einfacher schreiben:
  • \((\left\{abb^*\right\})^*ab^{\omega}\)
Die durch die beiden Teilausdrücke beschriebenen Wörter unterscheiden sich also dadurch, daß der erste Teilausdruck fordert, daß immer wieder a's kommen, während der zweite Teilausdruck auch unendlich viele b's hintereinander zuläßt.

Die Vereinigung beider Sprachen läßt sich also so beschreiben:
  • Unendliche lange Wörter aus a's und b's, in denen niemals zwei a aufeinander folgen.
amittelbach hat geschrieben:ch würde behaupten, der zweite Ausdruck ist durchaus Teil der Sprache des Automaten. Diese wird aber meiner Ansicht nach bereits vollständig durch den ersten Ausdruck beschrieben.
Nein, denn der Stern im ersten Teilausdruck läßt nur endlich viele b's zu, nicht unendlich viele. Das Wort abbbbb... wird also durch den ersten Teilausdruck nicht beschrieben.
Julius hat geschrieben:Vielleicht könnte auch jemand mal das prinzipielle Vorgehen zum Finden dieser Sprache erklären.
Du meinst vom Büchi-Automaten zur akzeptierten Sprache als Omega-Ausdruck? Ich versuche mal zu beschreiben, wie man beim Büchi-Automaten aus der Aufgabenstellung vorgehen kann. Das ist aber kein "prinzipielles Vorgehen" im Sinen eines Algorithmus', sondern eher eine Anleitung für Menschen, was man sich überlegen muß.

Wir müssen ja alle unendlichen Eingabefolgen beschreiben, die (1) den Automat überhaupt weiterarbeiten lassen und (2) dabei unendlich oft in einem akzeptierenden Zzustand vorbeikommen. Hier haben wir nun zwei akzeptierende Zustände, die wir nacheinander betrachten können.

Fangen wir mit q0 an. Wie sieht ein Zirkel aus, der unendlich oft durch q0 führt? Er wird immer wieder in q0 vorbeikommen, und dazwischen einen Weg von q0 nach q0 wählen. Wir suchen also alle Wege von q0 nach q0, die zwischendurch nicht über q0 führen. Einer davon ist zunächst ganz einfach
  • \(q_0q_1q_0\) für die Eingabe \(ab\).
Alternativ könnten wir aber durch
  • \(q_0q_2q_1q_0\) laufen für die Eingabe \(abb\).
Oder durch
  • \(q_0q_2q_2q_1q_0\) für die Eingabe \(abbbb\).
Oder durch
  • \(q_0q_2q_2q_2q_1q_0\) für die Eingabe \(abbbb\).
Nun können wir ja beliebig lange in q2 bleiben, wenn die Eingabe genug b's enthält. Alle diese Zirkel über q2 können wir als
  • \(q_0q_2^*q_1q_0\) für die Eingabe \(ab^*bb\)
beschreiben. Unser akzeptiertes Wort darf nun auf einem beliebigen Weg vom Startzustand in den Zustand q0 gelangen, bevor unsere Zirkel über q0 beginnen. Da q0 aber selbst der Startzustand ist, gibt es nur einen solchen Weg, der dem leeren Wort entspricht. Insgesamt erhalten wir also folgende Beschreibung der Eingabe, die einen unendlichen Zirkel auslöst, der immer wieder durch q0 führt:
  • \(\left\{ab,ab^*bb\right\})^{\omega}\).
Das ist gerade der erste Teilausdruck aus der Musterlösung. Er beschreibt alle Eingaben, die eine Ausführung unendlich oft durch q0 ermöglichen.

Nun betrachten wir analog den anderen akzeptierenden Zustand q2. Nun suchen wir alle Wege von q2 nach q2, die nicht durch q0 oder q2 führen. (Wir dürfen q0 ebenfalls ausschließen, denn solange immer mal wieder ein Weg genommen wird, der durch q0 führt, werden insgesamt unendlich viele Wege genommen, die durch q0 führen, und die entsprechende Eingabe wird durch den ersten Teilausdruck bereits erfasst. Es genügt also, alle Eingaben durch den zweiten Teilausdruck zu erfassen, die zwar akzeptiert werden, aber bisher nicht erfasst werden). Es gibt nur einen ganz einfachen Weg, der von q2 nach q2 führt, aber nicht durch q0 oder q2 kommt:
  • \(q_2q_2\) für die Eingabe \(b\).
Wenn eine Eingabe akzeptiert wird, aber nicht unendlich oft durch q0 geht, dann wird also irgendwann nur noch dieser Weg durch den Automaten abgearbeitet. Was darf davor passieren? Es darf irgendein Weg vom Startzustand zu q2 genommen werden. Insbesondere darf dieser Weg auch Zirkel enthalten und sogar zwischendurch mal bei q2 vorbeikommen. Von q0 kommen wir einfach durch die Eingabe a nach q2. Davor dürfen aber noch endlich beliebig viele Zirkel von q0 nach q0 kommen, die (wir wir ja schon wissen) durch
  • \(\left\{ab,ab^*bb\right\})^{*}\)
beschrieben werden können. (Wichtig: Diesmal mit Sternchen statt mit Omega). Insgesamt ergibt sich also der 2. Teilausdruck aus der Musterlösung:
  • \((\left\{ab,ab^*bb\right\})^*ab^{\omega}\)
Dieser Teilausdruck beschreibt alle Eingaben, die eine Ausführung unendlich oft durch q2, aber höchstens endlich oft durch q0 ermöglichen.

Nun könnnen wir diese beiden Teilausdrücke einfach als Alternative schreiben und erhalten die Musterlösung:
  • \(L(B_1)=\left\{(\left\{ab,ab^*bb\right\})^{\omega},(\left\{ab,ab^*bb\right\})^*ab^{\omega}\right\}\)

Julius
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 237
Registriert: 5. Okt 2005 15:52

Beitrag von Julius »

Vielen Dank! Mir war das mit den "nur noch b's lesen" nicht klar geworden aus der Lösung. Jetzt ist es klar.

MHK
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 27. Mär 2006 17:59

Beitrag von MHK »

Hallo,
ist

\(((ba)^* aaa)^\omega\)

eine mögliche Lösung für Hausaufgabe 2.2a(2.)?

Tillmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Beitrag von Tillmann »

MHK hat geschrieben:ist

\(((ba)^* aaa)^\omega\)

eine mögliche Lösung für Hausaufgabe 2.2a(2.)?
Ich würde sagen: Ja, das ist korrekt.

Benutzeravatar
tm_n
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 105
Registriert: 3. Nov 2005 17:16
Wohnort: Frankfurt am Main
Kontaktdaten:

Beitrag von tm_n »

Hallo,
ist meine Lösung auch "ok"

L(B1) = \((ab | ab^*bb )^\omega\)

für Übung 2.3a(3.)?
Zuletzt geändert von tm_n am 22. Mär 2007 14:41, insgesamt 1-mal geändert.
"Research works on disclosure, not on secrets"

MHK
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 27. Mär 2006 17:59

Beitrag von MHK »

@ Tillmann
Vielen Dank!

Benutzeravatar
michasch
DON'T PANIC
Beiträge: 42
Registriert: 2. Okt 2004 20:47
Wohnort: Dieburg
Kontaktdaten:

Beitrag von michasch »

tm_n hat geschrieben:Hallo,
ist meine Lösung auch "ok"

L(B1) = \((ab | ab^*bb )^\omega\)

für Hausaufgabe 2.3a(3.)?
1. gibt es kein | wie in regulären ausdrücken (statt (a|b) muss man {a,b} schreiben)
2. erkennt der Büchi-Automat auch Wörter, die nicht in deiner Sprache enthalten sind, z.B.: \(ab^\omega\)
Ich denke, also bin ich - manche sind trotzdem.

Benutzeravatar
tm_n
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 105
Registriert: 3. Nov 2005 17:16
Wohnort: Frankfurt am Main
Kontaktdaten:

Beitrag von tm_n »

danke für den hinweis.
"Research works on disclosure, not on secrets"

Benutzeravatar
dEeP-fRiEd
Kernelcompilierer
Kernelcompilierer
Beiträge: 432
Registriert: 19. Okt 2005 00:58
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von dEeP-fRiEd »

michasch hat geschrieben: 1. gibt es kein | wie in regulären ausdrücken (statt (a|b) muss man {a,b} schreiben)
Hm das war mir auch noch nicht bewusst. Darf man auch nicht a + b schreiben?
NOSCE TE IPSUM
visit: http://www.flicknetwork.net.tc

Andreas Schlosser
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 21. Okt 2005 10:35

Beitrag von Andreas Schlosser »

Ob ihr (a|b) oder {a,b} schreibt ist mir egal. a + b bitte nicht, dass könnte man verwechseln mit a^+b

Antworten

Zurück zu „Archiv“