NFA - reg. Ausdruck < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:22 Di 16.11.2010 | | Autor: | Lovelace |
| Aufgabe | Ein DFA M ({a,b}, ( [mm] z_{0}, z_{1}, z_{2}, z_{3}, z_{4}), \delta, (z_{0}), (z_{4}) [/mm] ) sei gegeben mit
[mm] z_{0}a [/mm] --> [mm] z_{1}
[/mm]
[mm] z_{0}b [/mm] --> [mm] z_{3}
[/mm]
[mm] z_{1}a [/mm] --> [mm] z_{2}
[/mm]
[mm] z_{1}b [/mm] --> [mm] z_{4}
[/mm]
[mm] z_{2}a [/mm] --> [mm] z_{1}
[/mm]
[mm] z_{2}b [/mm] --> [mm] z_{4}
[/mm]
[mm] z_{3}a [/mm] --> [mm] z_{1}
[/mm]
[mm] z_{3}b [/mm] --> [mm] z_{0}
[/mm]
[mm] z_{4}a [/mm] --> [mm] z_{4}
[/mm]
[mm] z_{4}b [/mm] --> [mm] z_{4}
[/mm]
a) Bestimmen Sie den zu M äquivalenten Minimalautomaten mit dem Algorithmus aus der Vorlesung
b) Welche Sprache akzeptiert M? Lösen Sie dazu das entsprechende Gleichungssystem
c) Geben Sie eine rechtslineare Grammatik G an, für die L(g) = L(M) gilt. |
Meine Frage dreht sich um Teilaufgabe b)
Das Gleichungssystem habe ich wie folgt aufgestellt:
[mm] z_{0} [/mm] = [mm] az_{1} \cup bz_{3} [/mm] (I)
[mm] z_{1} [/mm] = [mm] az_{2} \cup bz_{4} [/mm] (II)
[mm] z_{2} [/mm] = [mm] az_{1} \cup bz_{4} [/mm] (III)
[mm] z_{3} [/mm] = [mm] bz_{0} \cup az_{1} [/mm] (IV)
[mm] z_{4} [/mm] = [mm] az_{4} \cup bz_{4} [/mm] (V)
ich setze also (II) in (I) ein:
[mm] z_{0} [/mm] = [mm] aaz_{2} \cup abz_{4} \cup bz_{3} [/mm]
--> liege ich bis hierhin überhaupt richtig?
Irgendwie sehe ich den Sinn des Ganzen im Moment nicht wirklich, da ich durch weiteres Einsetzen es nie schaffe, irgendetwas zu eliminieren!
Kann mir da jemand einen Tipp geben?
Vielen vielen Dank!
Ada
P.S.: die Frage hab ich natürlich nur hier gepostet!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:05 Mi 17.11.2010 | | Autor: | felixf |
Moin Ada!
Ich hab solche Geichungssysteme noch nie gesehen, aber ich versuch trotzdem mal zu antworten ;)
> Ein DFA M ({a,b}, ( [mm]z_{0}, z_{1}, z_{2}, z_{3}, z_{4}), \delta, (z_{0}), (z_{4})[/mm]
> ) sei gegeben mit
> [mm]z_{0}a[/mm] --> [mm]z_{1}[/mm]
> [mm]z_{0}b[/mm] --> [mm]z_{3}[/mm]
> [mm]z_{1}a[/mm] --> [mm]z_{2}[/mm]
> [mm]z_{1}b[/mm] --> [mm]z_{4}[/mm]
> [mm]z_{2}a[/mm] --> [mm]z_{1}[/mm]
> [mm]z_{2}b[/mm] --> [mm]z_{4}[/mm]
> [mm]z_{3}a[/mm] --> [mm]z_{1}[/mm]
> [mm]z_{3}b[/mm] --> [mm]z_{0}[/mm]
> [mm]z_{4}a[/mm] --> [mm]z_{4}[/mm]
> [mm]z_{4}b[/mm] --> [mm]z_{4}[/mm]
>
> a) Bestimmen Sie den zu M äquivalenten Minimalautomaten
> mit dem Algorithmus aus der Vorlesung
>
> b) Welche Sprache akzeptiert M? Lösen Sie dazu das
> entsprechende Gleichungssystem
>
> c) Geben Sie eine rechtslineare Grammatik G an, für die
> L(g) = L(M) gilt.
> Meine Frage dreht sich um Teilaufgabe b)
>
> Das Gleichungssystem habe ich wie folgt aufgestellt:
>
> [mm]z_{0}[/mm] = [mm]az_{1} \cup bz_{3}[/mm] (I)
> [mm]z_{1}[/mm] = [mm]az_{2} \cup bz_{4}[/mm] (II)
> [mm]z_{2}[/mm] = [mm]az_{1} \cup bz_{4}[/mm] (III)
> [mm]z_{3}[/mm] = [mm]bz_{0} \cup az_{1}[/mm] (IV)
> [mm]z_{4}[/mm] = [mm]az_{4} \cup bz_{4}[/mm] (V)
>
> ich setze also (II) in (I) ein:
>
> [mm]z_{0}[/mm] = [mm]aaz_{2} \cup abz_{4} \cup bz_{3}[/mm]
> --> liege ich bis hierhin überhaupt richtig?
Ich denke schon.
Du kannst doch auch noch (II) in (III) und (IV) einsetzen. Dann hast du:
> [mm]z_{0} = aaz_{2} \cup abz_{4} \cup bz_{3}[/mm] (I')
> [mm]z_{1} = az_{2} \cup bz_{4}[/mm] (II)
> [mm]z_{2} = aaz_2 \cup abz_4 \cup bz_{4}[/mm] (III')
> [mm]z_{3} = bz_{0} \cup aaz_2 \cup abz_4[/mm] (IV')
> [mm]z_{4} = az_{4} \cup bz_{4}[/mm] (V)
Gleichung (II) kannst du nun weglassen, da [mm] $z_1$ [/mm] sonst nicht mehr vorkommt.
> [mm]z_{0} = aaz_{2} \cup abz_{4} \cup bz_{3}[/mm] (I')
> [mm]z_{2} = aaz_2 \cup abz_4 \cup bz_{4}[/mm] (III')
> [mm]z_{3} = bz_{0} \cup aaz_2 \cup abz_4[/mm] (IV')
> [mm]z_{4} = az_{4} \cup bz_{4}[/mm] (V)
Jetzt kannst du (I') in (IV') einsetzen:
> [mm]z_{3} = baaz_{2} \cup babz_{4} \cup bbz_{3} \cup aaz_2 \cup abz_4[/mm] (IV'')
Damit hast du:
> [mm]z_{0} = aaz_{2} \cup abz_{4} \cup bz_{3}[/mm] (I')
> [mm]z_{2} = aaz_2 \cup abz_4 \cup bz_{4}[/mm] (III')
> [mm]z_{3} = baaz_{2} \cup babz_{4} \cup bbz_{3} \cup aaz_2 \cup abz_4[/mm] (IV'')
> [mm]z_{4} = az_{4} \cup bz_{4}[/mm] (V)
Ich weiss nicht, ob das irgendwie weiter hilft.
Eventuell ist es besser, erst den Minimalautomaten in (a) aufzustellen und dann fuer diesen das Gleichungssystem hinzuschreiben?
Und was genau sollen die Geichungen machen? Reguaere Ausdruecke finden (wie ![[]](/images/popup.gif) hier auf Seite 31)?
In dem Fall geht das doch so besser:
> [mm]z_{0}[/mm] = [mm]az_{1} \cup bz_{3}[/mm] (I)
> [mm]z_{1}[/mm] = [mm]az_{2} \cup bz_{4}[/mm] (II)
> [mm]z_{2}[/mm] = [mm]az_{1} \cup bz_{4}[/mm] (III)
> [mm]z_{3}[/mm] = [mm]bz_{0} \cup az_{1}[/mm] (IV)
> [mm]z_{4}[/mm] = [mm]az_{4} \cup bz_{4}[/mm] (V)
Bei (V) sieht man sofort, dass [mm] $z_4$ [/mm] dem Ausdruck [mm] $(a|b)^\ast$ [/mm] entspricht (und die Gleichung muesste doch eigenlich [mm] $z_4 [/mm] = a [mm] z_4 \cup [/mm] b [mm] z_4 \cup \varepsilon$ [/mm] lauten?). Einsetzen dieses Ausdrucks in (II) und (III) liefert
> [mm]z_{0}[/mm] = [mm]az_{1} \cup bz_{3}[/mm] (I)
> [mm]z_{1}[/mm] = [mm]az_{2} \cup b(a|b)^\ast[/mm] (II')
> [mm]z_{2}[/mm] = [mm]az_{1} \cup b(a|b)^\ast[/mm] (III')
> [mm]z_{3}[/mm] = [mm]bz_{0} \cup az_{1}[/mm] (IV)
Einsetzen von (IV) in (I) gibt
> [mm]z_{0}[/mm] = [mm]az_{1} \cup bbz_0 \cup baz_1[/mm] (I')
> [mm]z_{1}[/mm] = [mm]az_{2} \cup b(a|b)^\ast[/mm] (II')
> [mm]z_{2}[/mm] = [mm]az_{1} \cup b(a|b)^\ast[/mm] (III')
Wenn man sich jetzt (II') in (III') einsetzt, erhaelt man
> [mm]z_{0}[/mm] = [mm]az_{1} \cup bbz_0 \cup baz_1[/mm] (I')
> [mm]z_{1}[/mm] = [mm]az_{2} \cup b(a|b)^\ast[/mm] (II')
> [mm]z_{2}[/mm] = [mm]aaz_2 \cup ab(a|b)^\ast \cup b(a|b)^\ast[/mm] (III')
Man sieht also, dass (III') gleich [mm] $z_2 [/mm] = [mm] a^\ast [/mm] b [mm] (a|b)^\ast$ [/mm] ist. Das eingesetzt bei (II') ergibt
> [mm]z_{0}[/mm] = [mm]az_{1} \cup bbz_0 \cup baz_1[/mm] (I')
> [mm]z_{1}[/mm] = [mm]a a^\ast b (a|b)^\ast \cup b(a|b)^\ast[/mm] (II'')
Auch bei (II'') sieht man sofort, dass dies gleich [mm] $z_1 [/mm] = [mm] a^\ast [/mm] b (a | [mm] b)^\ast$ [/mm] ist. Einsetzen in (I') liefert
> [mm]z_{0}[/mm] = [mm]aa^\ast b (a | b)^\ast \cup bbz_0 \cup baa^\ast b (a | b)^\ast[/mm] (I'')
Das [mm] $z_0 \to bbz_0$ [/mm] kann man in
> [mm]z_{0}[/mm] = [mm](bb)^\ast aa^\ast b (a | b)^\ast \cup (bb)^\ast baa^\ast b (a | b)^\ast[/mm] (I''')
umschreiben, was dann gleich
> [mm]z_{0}[/mm] = [mm]b^\ast aa^\ast b (a | b)^\ast[/mm] (I'''')
wird. Und schon haben wir einen regulaeren Ausdruck, der die vom Automaten akzeptierte Sprache beschreibt.
Vielleicht hilft das etwas weiter... :)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:57 Do 18.11.2010 | | Autor: | Lovelace |
juhuuu...ja, genau das ist es, was ich erreichen will! Einen regulären Ausdruck zu erzeugen, der die Sprache beschreibt! Dankeschön!
|
|
|
|
Wie es genau geht sollte in dem verlinkten Skript stehen, oder halt auch bei euch im Skript.
