DEA zu NEA transformieren < Sonstige < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:54 Sa 18.04.2009 | | Autor: | hasso |
Hallo zusammen!
Ich beschäftige gerade damit wie man einen DEA in einen NEA transformieren kann. Dabei stellen sich jedoch mehrere Frage auf die ich bis jetzt noch keine antwort hab.
Und zwar, ein DEA kann ja immer nur einen Zustand annehmen wobei ein NEA mehrere Zustände annehmen kann.
Und aus jeden NEA kann man einen DEA kontruieren und umgekehrt.
Das ist mir bis jetzt klar...
1)
Meine Frage, wenn ich auch einen DEA bspw. einen NEA konstruiere gibts dafür nur
eine Lösung oder kann man verschiedene richtige kontruitionen erstellen?
2)
Ist es schwieriger aus einen NEA ein DEA zu kontruiren oder umgekehrt?
Vielleicht noch eine erklärung...wär ganz lieb =)
3) Gibts eine bestimmte vorgehensweise bei der transformation, die man
beachten sollte?
Danke im vorraus =)
lg hasso
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:56 So 19.04.2009 | | Autor: | thane |
hallo,
> 1)
> Meine Frage, wenn ich auch einen DEA bspw. einen NEA
> konstruiere gibts dafür nur
> eine Lösung oder kann man verschiedene richtige
> kontruitionen erstellen?
>
Hallo,
zu 1) Wenn du einen Automaten (NEA/DEA) konstruieren willst, der eine bestimmte Sprache erkennt, gibt es viele verschiedene Konstruktionen, die Alle das Selbe leisten. (indem du z.B. noch unnötige Zustände dazunimmst, kannst du den Automaten beliebig aufblähen).
Allerdings ist der kleinste (bezüglich der Anzahl der Zustände) DEA, der eine Sprache erkennt, immer eindeutig. Stichwort: Minimalautomat.
> 2)
> Ist es schwieriger aus einen NEA ein DEA zu kontruiren
> oder umgekehrt?
> Vielleicht noch eine erklärung...wär ganz lieb =)
> Und zwar, ein DEA kann ja immer nur einen Zustand annehmen wobei
> ein NEA mehrere Zustände annehmen kann.
Da hast du ja schon die Erklärung geliefert. Ein DEA ist ein Spezialfall eines NEA's, soll heißen, ein DEA ist auch immer ein NEA! Dementsprechend ist auch nur die Transformation NEA -> DEA interessant.
> 3) Gibts eine bestimmte vorgehensweise bei der
> transformation, die man
> beachten sollte?
![[]](/images/popup.gif) http://de.wikipedia.org/wiki/Potenzmengenkonstruktion
Der Algorithmus ist recht intuitiv und nach ein paar Übungen geht die Umwandlung fast automatisch.
gruß,
thane
> Danke im vorraus =)
>
> lg hasso
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:10 So 19.04.2009 | | Autor: | hasso |
hallo thane,
dankee für deine antwort habs jetzt auf jeden fall verstanden =)
ich hab auch mal mit einer transformation begonnen, eine kleinigkeit weiß ich leider nicht so genau und zwar..
gegeben ist bspw. eine Tabelle für einen NEA aus diser tabelle möcht nun die Tabell für den DEA kontruieren.
[Dateianhang nicht öffentlich]
So nun muss man dafür alle verschiedenen paare benutzen. sprich es sind an diesem beispiel 8 weil 2 werte angenommen werden können {1,0} und 3 Zustände vorliegen. [mm] 2^3= [/mm] 8
Was ich nicht weiß wie man auf diese verschiedenen paare schnell kommen kann, ich mein in der klausur muss das ja flott gehen gibts dafür irend ein trick wie man direkt auf die verschiedenen paare herleiten kann die ich rot makiert habe?
viele Grüße
hasso
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:41 So 19.04.2009 | | Autor: | thane |
Huhu,
Erstmal ![[ok]](/images/smileys/ok.gif "[ok]") dein DEA sieht richtig aus.
Bei den meisten Aufgaben treten nicht immer alle Paarkombinationen auf. Dein Beispiel ist jetzt mal ne Ausnahme.
Für die Klausur einfach wie immer vorgehen, angefangen beim Startzustand, ablesen welche Zustände er bei Eingabe eines Zeichens aus dem Alphabet erreicht, diese als einen neuen Zustand aufschreiben und damit weitermachen.
Wenn du also z.B.: beim Zustand [mm] \{s_0,s_2\} [/mm] bist und [mm] \delta' [/mm] für die 0 ausrechnen willst, ließt du einfach in deinem NEA ab, welche Zustände von [mm] s_0 [/mm] bei Eingabe von 0 und welche von [mm] s_2 [/mm] erreichbar sind und diese bilden den neuen Zustand.
Da du außerdem in der Klausur unter Zeitdruck stehst, wird es auch kein extrem Aufwendiger NEA sein, da Sie ja nur kontrollieren wollen ob du das Prinzip verstanden hast (normalerweise).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:24 Mo 20.04.2009 | | Autor: | hasso |
hallo thane,
mich verwird gerade eine sache so richtig....und zwar auf wikipedia also den link den du mich geschickt hast ist ein beispiel...
NEA Tabelle:
δ a b
s0 {s0,s1} {s0}
s1 kein zust. {s2}
s2 {s3} kein zust.
s3 kein zust. kein zust.
So und bei der NEA Tabelle:
δ' a b
s0' = {s0} {s0,s1} {s0}
s1' = {s0,s1} {s0,s1} {s0,s2}
s2' = {s0,s2} {s0,s1,s3} {s0}
s3' = {s0,s1,s3} {s0,s1} {s0,s2}
also unter dem link:
http://de.wikipedia.org/wiki/Potenzmengenkonstruktion
ist in bissel deutlicher als meins :D
also was mich total verwird ist, das nicht die paare
s0,s2,s3
s0,s3
unter anderem auftauchen,...sprich woher weiß man den wo das minimum an paarenvorliegt.
ich mein ich hätte alle paare hingeschrieben, wär aber unnnöti gewesen wie man sieht
lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:13 Mo 20.04.2009 | | Autor: | thane |
Hallo hasso,
ließ dir nocheinmal den Algorithmus durch, dann sollte klar werden welche neuen Zustände du benötigst. Dennoch meine ich, dass hier auch ein ausführliches Beispiel viel Wert ist, deshalb mach ich mal die Umwandlug des Wiki Beispiels explizit vor. Gegeben also der NEA anhand der Übergangstabelle:
[mm] \vmat{ \delta & a & b \\ s_0 & \{s_0,s_1\} & \{s_0\} \\ s_1 & \emptyset & \{s_2\} \\ s_2 & \{s_3\} & \emptyset \\ s_3 & \emptyset & \emptyset }
[/mm]
Wir beginnen nun mit dem Berechnen der Zustände für unseren DEA mit Übergangsfunktion [mm] \delta' [/mm] angefangen bei [mm] s_0 [/mm]:
[mm] \vmat{ \delta' & a & b \\ s_0 ' := \{s_0\} & \{s_0,s_1\} & \{s_0\} } [/mm]
Bei Eingabe von [mm]a[/mm], in [mm] s_0[/mm] landen wir in dem Zustand [mm] \delta(s_0,a) = \{s_0,s_1\} =: s_1' [/mm] und mit Eingabe [mm] b [/mm] wieder im Startzustand [mm]\delta(s_0,b) = \{s_0\} =: s_0' [/mm]. Die Übergangsfunktion von [mm] s_0' [/mm] haben wir bereits berechnet, also fehlt nurnoch [mm] s_1' [/mm].
[mm] \vmat{ \delta' & a & b \\ s_0 ' := \{s_0\} & \{s_0,s_1\} & \{s_0\} \\ s_1 ' := \{s_0,s_1\} & \{s_0,s_1\} & \{s_0,s_2\}} [/mm]
Dabei berechnet sich [mm] \delta'(s_1',a) [/mm] indem wir in unserem NEA ablesen welche Zustände von [mm] \delta(s_0,a) [/mm] und [mm] \delta(s_1,a) [/mm] erreicht werden.
Analog für [mm] \delta'(s_1',b) [/mm] mit [mm] \delta(s_0,b) = \{s_0\} [/mm] und [mm] \delta(s_1,b) = \{s_2\}[/mm] ergibt sich
[mm] \delta'(s_1',b) = \{s_0,s_2\} := s_2'[/mm]
Du siehst also, die neuen Zustände ergeben sich während der Berechnung, nun fehlen noch die Übergänge für [mm] s_2' [/mm].
[mm] \vmat{ \delta' & a & b \\ s_0 ' := \{s_0\} & \{s_0,s_1\} & \{s_0\} \\ s_1 ' := \{s_0,s_1\} & \{s_0,s_1\} & \{s_0,s_2\} \\ s_2 ' := \{s_0,s_2\} & \{s_0,s_1,s_3\} & \{s_0\}} [/mm]
Für [mm] \delta'(s_2',a) [/mm] geht man genauso vor wie bei [mm] s_1' [/mm]. [mm] \delta'(s_2',b) [/mm] hat eine kleine Besonderheit, denn es gilt [mm] \delta(s_0,b) = \{s_0\} [/mm] und [mm] \delta(s_2,b) =\emptyset [/mm]
Wir erzeugen nun keinen Zustand [mm] \{s_0, \emptyset \} [/mm], da wir den Fehlerzustand verwerfen können, falls noch mindestens ein Zustand (in diesem Fall [mm] s_0 [/mm]) erreicht wird. (Richtig wäre natürlich auch [mm] \{s_0, \emptyset \} [/mm], doch damit blähen wir den Automaten stark auf und erzeugen unnötig viele Zustände) Damit ist dann [mm] \delta'(s_2',b) = \{s_0\}[/mm].
Für den neu entstandenen Zustand [mm] s_3' := \{s_0,s_1,s_3\} [/mm] gehen wir analog vor und erhalten schließlich:
[mm] \vmat{ \delta' & a & b \\ s_0 ' := \{s_0\} & \{s_0,s_1\} & \{s_0\} \\ s_1 ' := \{s_0,s_1\} & \{s_0,s_1\} & \{s_0,s_2\} \\ s_2 ' := \{s_0,s_2\} & \{s_0,s_1,s_3\} & \{s_0\} \\ s_3 ' := \{s_0,s_1,s_3\} & \{s_0,s_1\} & \{s_0,s_2\}} [/mm]
Dabei sind keine neuen Zustände mehr hinzugekommen und wir sind fertig.
gruß,
thane
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:02 Mo 20.04.2009 | | Autor: | hasso |
Hallo thane,
erstmal dickes danke für die mühe......
also ich habs mir mal angeguckt, aber ich kann nicht alles so nachvoll ziehen weil ich das so verstanden habe wie's unten geposted hab, hab ebenfalls hier auch nur den Zustand a berücksichtigt.
Es berechnet sich [mm] s_0' [/mm] = [mm] \delta(s_0,a)
[/mm]
Es berechnet sich [mm] s_1' [/mm] = [mm] \delta(s_0,a) [/mm] und aus [mm] \delta(s_1,a) [/mm]
Es berechnet sich [mm] s_2' [/mm] = [mm] \delta(s_0,a) [/mm] und aus [mm] \delta(s_1,a), [/mm] und [mm] \delta(s_2,a), [/mm]
Es berechnet sich [mm] s_3' [/mm] = [mm] \delta(s_0,a) [/mm] und aus [mm] \delta(s_1,a) [/mm] und [mm] \delta(s_2,a) [/mm] und [mm] \delta(s_3,a)
[/mm]
Viele grüße
hasso
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:17 Mo 20.04.2009 | | Autor: | thane |
Hallo hasso,
irgendwo ist noch ein kleines Missverständins das wir beseitigen müssen.
Zunächsteinmal definieren wir den Zustand [mm] s_0' := \{s_0\}[/mm] und erhalten dann
$ [mm] \vmat{ \delta' & a & b \\ s_0 ' := \{s_0\} & \{s_0,s_1\} & \{s_0\} } [/mm] $
(Beachte, dass es einen großen Unterschied zwischen zwischen den [mm] s_n [/mm] und den [mm] s_n' [/mm] gibt!) Jetzt sehen wir, dass [mm] \delta' (s_0',a) = \{s_0,s_1\} [/mm] ein Zustand ist, den wir noch nicht links in unserer Liste stehen haben. Also definieren wir nun [mm] s_1' := \{s_0,s_1\} [/mm] (Wir hätten den Zustand auch [mm]s_{42} [/mm] oder Apfel nennen können :) ) Wie im Vorpost beschrieben (ist dir das Vorgehen klar?) erhalten wir dann:
$ [mm] \vmat{ \delta' & a & b \\ s_0 ' := \{s_0\} & \{s_0,s_1\} & \{s_0\} \\ s_1 ' := \{s_0,s_1\} & \{s_0,s_1\} & \{s_0,s_2\}} [/mm] $
Wieder erkennen wir einen uns unbekannten Zustand und definieren ihn schnell als [mm] s_2' := \{s_0,s_2\} [/mm] usw. ...
>
>Es berechnet sich $ [mm] s_0' [/mm] $ = $ [mm] \delta(s_0,a) [/mm] $ Achtung! $ [mm] \delta(s_0,a) [/mm] = [mm] s_0 [/mm] $ aber [mm] s_0' [/mm] = [mm] \{s_0\} [/mm] auch wenn ich das im Vorpost etwas lasch gehandhabt habe.
>
>Es berechnet sich $ [mm] s_1' [/mm] $ = $ [mm] \delta(s_0,a) [/mm] $ und aus $ [mm] \delta(s_1,a) [/mm] $
>
>Es berechnet sich $ [mm] s_2' [/mm] $ = $ [mm] \delta(s_0,a) [/mm] $ und aus $ [mm] \delta(s_1,a), [/mm] $ und $ [mm] \delta(s_2,a), [/mm] $
>
>Es berechnet sich $ [mm] s_3' [/mm] $ = $ [mm] \delta(s_0,a) [/mm] $ und aus $ [mm] \delta(s_1,a) [/mm] $ und $ [mm] \delta(s_2,a) [/mm] $ und $ [mm] \delta(s_3,a) [/mm] $
Wenn du hierzu noch etwas schreiben könntest warum du so vorgehst ? Denn im Allgemeinen ist das sicherlich nicht richtig.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:12 Mo 20.04.2009 | | Autor: | hasso |
hallo thane,
das es sich um ein kleines missverständnis handelt hört sich schonmal motevieren an =)
Ich drücks mal ganz einfach aus.....ich kann gar nicht nachvollziehen warum in [mm] s_0 [/mm] ' in den eckigen klammern [mm] s_0 [/mm] drin steht -> [mm] {s_0}
[/mm]
oder warum im [mm] \delta' s_1' [/mm] in den eckigenklammern [mm] s_0 [/mm] und [mm] s_1 [/mm] drin steht
und warum in [mm] \delta' s_2' [/mm] in den eckigenklammern [mm] s_0 [/mm] und [mm] s_2 [/mm] drin steht
und das in [mm] \delta' s_3' [/mm] in den eckkgenklammern [mm] s_0 [/mm] und [mm] s_1 [/mm] und [mm] s_3 [/mm] drin steht...
ich mein warum steht nicht in [mm] s_3' [/mm] bspw. nur [mm] s_0 [/mm] und [mm] s_3 [/mm]
also den rest hast du ja gut erklärt und hab ich eigentlich verstanden...nur wie gesagt das versteh ich nicht..wie diese konstelationen zustande kommen.
$ [mm] \vmat{ \delta' & a & b \\ s_0 ' := \{s_0\} & \{s_0,s_1\} & \{s_0\} \\ s_1 ' := \{s_0,s_1\} & \{s_0,s_1\} & \{s_0,s_2\} \\ s_2 ' := \{s_0,s_2\} & \{s_0,s_1,s_3\} & \{s_0\} \\ s_3 ' := \{s_0,s_1,s_3\} & \{s_0,s_1\} & \{s_0,s_2\}} [/mm] $
Viele grüße
hasso
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:53 Mo 20.04.2009 | | Autor: | thane |
hallo hasso,
Das Problem kriegen wir auch noch gelöst.
> Ich drücks mal ganz einfach aus.....ich kann gar nicht
> nachvollziehen warum in [mm]s_0[/mm] ' in den eckigen klammern [mm]s_0[/mm]
> drin steht -> [mm]{s_0}[/mm]
>
> oder warum im [mm]\delta' s_1'[/mm] in den eckigenklammern [mm]s_0[/mm] und
> [mm]s_1[/mm] drin steht
>
> und warum in [mm]\delta' s_2'[/mm] in den eckigenklammern [mm]s_0[/mm] und
> [mm]s_2[/mm] drin steht
>
> und das in [mm]\delta' s_3'[/mm] in den eckkgenklammern [mm]s_0[/mm] und [mm]s_1[/mm]
> und [mm]s_3[/mm] drin steht...
>
> ich mein warum steht nicht in [mm]s_3'[/mm] bspw. nur [mm]s_0[/mm] und [mm]s_3[/mm]
>
> also den rest hast du ja gut erklärt und hab ich eigentlich
> verstanden...nur wie gesagt das versteh ich nicht..wie
> diese konstelationen zustande kommen.
Ok schauen wir nochmal den Algorithmus auf Wiki an.Punkt 2: Wir fangen an, indem wir unseren Startzustand für den neuen DEA definieren. Den nenn ich jetzt mal [mm] q_{start} [/mm] damit keine Verwirrung mehr entsteht und man besser sieht, dass [mm] s_i [/mm] und [mm] s_i'[/mm] völlig verschieden sind!
Also [mm] q_{start} := \{s_0\} [/mm] und mit (3) erhalten wir dann sofort
$ [mm] \vmat{ \delta' & a & b \\ q_{start} & \{s_0,s_1\} & \{s_0\}} [/mm] $
Nun müssen wir noch [mm] \{s_0,s_1\} [/mm] bearbeiten. Dies definieren wir mal durch [mm] q_{info} := \{s_0,s_1\} [/mm]
Verfahren wir weiter nach dem Algo:
$ [mm] \vmat{ \delta' & a & b \\ q_{start} & \{s_0,s_1\} & \{s_0\} \\q_{info} & \{s_0,s_1\} & \{s_0,s_2\} \\q_{buch} & \{s_0,s_1,s_3\} & \{s_0\} \\q_{auto}& \{s_0,s_1\} & \{s_0,s_2\}} [/mm] $
Wobei [mm] q_{buch} := \{s_0,s_2\}, q_{auto} := \{s_0,s_1,s_3\} [/mm]. Wenn dir vllt. das Umdefinieren nicht gefällt, man muss das ja nicht tun, es dient schließlich nur der Übersichtlichkeit.
[mm]\vmat{ \delta' & a & b \\ \{s_0\} & \{s_0,s_1\} & \{s_0\} \\ \{s_0,s_1\} & \{s_0,s_1\} & \{s_0,s_2\} \\ \{s_0,s_2\} & \{s_0,s_1,s_3\} & \{s_0\} \\ \{s_0,s_1,s_3\} & \{s_0,s_1\} & \{s_0,s_2\}}[/mm]
> oder warum im [mm] s_1'[/mm] in den eckigenklammern [mm]s_0[/mm] und
> [mm]s_1[/mm] drin steht
Warum ist das so ? Nun [mm] $\delta'(\{s_0\},a)$ [/mm] erzeugt einen Neuen Zustand dem wir einfach einen Namen geben in diesem Fall eben [mm] $s_1'$ [/mm] mehr steckt nicht dahinter. Genauso erzeugt [mm] $\delta'(\{s_0,s_2\},a) =\{s_0,s_1,s_3\}$ [/mm] einen neuen Zustand dem wir den Namen [mm] $s_2'$ [/mm] gegeben haben.
gruß,
thane
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:21 Di 21.04.2009 | | Autor: | hasso |
hallo thane,
ich glaub du hast mich wieder falsch verstanden, oder ich hab mich falsch ausgedrückt.....ich veruschs noch einmal
alsooooo
wie sich die 2 spalte und 3 spalte ergibt ist nun klar. aber wie sich die erste spalte ergibt ist unklar. ich weiß auch das sich spalte 2 und 3 aus spalte 1 ergibt. Nur wie ergibt sich spalte 1.
$ [mm] \vmat{ \delta' & a & b \\ \{s_0\} & \{s_0,s_1\} & \{s_0\} \\ \{s_0,s_1\} & \{s_0,s_1\} & \{s_0,s_2\} \\ \{s_0,s_2\} & \{s_0,s_1,s_3\} & \{s_0\} \\ \{s_0,s_1,s_3\} & \{s_0,s_1\} & \{s_0,s_2\}} [/mm] $
gruß hasso
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:43 Di 21.04.2009 | | Autor: | thane |
huhu hasso,
ja ok dann haben wir aneinander vorbei geredet sorry :)
Wie sich die erste Zeile ergibt sollte klar sein, grob gesagt den Startzustand und die davon erreichbaren Zustände in Klammern setzen. Wenn jetzt in der 2ten oder 3ten Spalte ein Zustand auftaucht, der noch nicht in der ersten Spalte steht, so schreibe ihn in die erste Spalte und rechne wieder [mm] $\delta'$ [/mm] für diesen Zustand und die Eingaben in diesem Fall a und b aus.
[mm]\vmat{ \delta' & a & b \\ \{s_0\} & \{s_0,s_1\} & \{s_0\}}[/mm]
[mm]\vmat{ \delta' & a & b \\ \{s_0\} & \{s_0,s_1\} & \{s_0\}\\ \{s_0,s_1\} }[/mm]
Hast du alle neu entstandenen Zustände bearbeitet, so bist du fertig.
gruß,
thane
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:27 Mi 22.04.2009 | | Autor: | hasso |
hallo thane,
ahsoooo dankeee ist ja voll easy dann :D
also stimmt das so, vom startzustand, ist der erreichbare ZUSTAND erstmal s1 und von s1 taucht dann eingabe bei b s0 und s2 auf und da das noch nicht in der ersten spalte steht, wird das dort hinzugefügt. Und bei einer eingabe von a bei s0 und s2 entsteht s0, s1, s3 der steht wiederum nicht in der ersten spalte und wird deswegen in der ersten Spalte hinzugefügt .?
korrekt soooo ne?
thxxx
gruß hasso
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:10 Mi 22.04.2009 | | Autor: | thane |
hallo hasso,
> also stimmt das so, vom startzustand, ist der erreichbare
> ZUSTAND erstmal s1 und von s1 taucht dann eingabe bei b s0 (ich denke du meinst mit [mm] $s_1$ [/mm] bestimmt: [mm] $s_1' [/mm] := [mm] \{s_0,s_1\}$)
[/mm]
> und s2 auf und da das noch nicht in der ersten spalte
> steht, wird das dort hinzugefügt. Und bei einer eingabe von
> a bei s0 und s2 entsteht s0, s1, s3 der steht wiederum
> nicht in der ersten spalte und wird deswegen in der ersten
> Spalte hinzugefügt .?
>
>
> korrekt soooo ne?
Ansonsten alles richtig , nun können die NEA's kommen.
gruß,
thane
|
|
|
|
