PDA

View Full Version : [Frage] 2.5

MrGoatee
19-10-2007, 18:02
Hab 2.5 jetzt einige male durchgerechnet, und krieg jedes mal das gleiche raus (siehe anhang, einmal nach Berechnung und dann minimiert)
Kann es echt so einfach sein?
freeye
20-10-2007, 18:24
schaut so aus - du hast aber die fallen vergessen.. q0,b und q3,a

edit - wie sähe denn die sprache aus? damit hab ich bissi probleme
thoreon
20-10-2007, 19:10
Hi,

Also irgendwie fehlt mir bei deinem Automaten der b-Zweig, d.h. wenn du vom Startpunkt mit b weggehen willst.

Ich hab folgende Übergangsfunktion:
delta dach - a - b
{q0} {q1,q2} {q3}
{q1,q2} {} {q1,q3,q4}
{q3} {q5} {}
{q1,q3,q4} {q1,q2,q5} {}
{q5} {} {}
{q1,q2,q5} {} {q1,q3,q4}

--> Der a-Zweig stimmt damit überein, aber wo ist der b-Zweig?

Bzgl. akzeptierte Sprache muss ich auch noch nachdenken ;-)

Danke und lg
Thomas

EDIT: Sorry, hab erst jetzt gesehen, dass freeye das gleiche gesehen hat, nur anders ausgedrückt :-)
FloW07
21-10-2007, 22:42
Anbei befindet sich meine Lösung

Bitte Feedback, ob ich den Graph richtig konvertiert habe..


thx

flo
FloW07
21-10-2007, 22:45
Anbei die Sprache vom DEA:
freeye
21-10-2007, 23:22
@flow07 2 mal q0 ??
rinf
22-10-2007, 01:06
{\epsilon} u ({a}{a,b}*)
MrGoatee
22-10-2007, 10:47
schaut so aus - du hast aber die fallen vergessen..

Ich hab den b-zweig (die Falle) bewusst weggelassen, laut Skriptum S.18 (von März 2004 von Fermüller und Salzer, also Seitenzahl kann eine andere sein)
Bei der graphischen Darstellung wird wie in Abb. 1.5 üblicherweise die Falle weggelassen, da die Fehlerübergänge die Darstellung komplexer, aber nicht informativer machen würde.Darf man nun oder darf man nicht?
tonico
22-10-2007, 15:13
Ich hab den b-zweig (die Falle) bewusst weggelassen, laut Skriptum S.18 (von März 2004 von Fermüller und Salzer, also Seitenzahl kann eine andere sein)
Darf man nun oder darf man nicht?

Klar, man darf die Fallen in der graphischen Darstellung weglassen.

Hier mein Vorschlag für die Übergangsfunktion (inkl. Falle) für den DEA B = <{p0, p1, p2}, {a, b}, λ, p0, {p0, p1}> mit anderen Buchstaben als beim Automaten der Angabe:

λ | a b
---+--------
p1 | p2 p3
p2 | p3 p1
p3 | p3 p3

{\epsilon} u ({a}{a,b}*)

In dieser Menge ist z.B. das Wort "aaa" enthalten welches der Automat nicht akzeptiert falls ich nicht irre.

Mein Vorschlag wäre: {ε, a} U {ab}+ · {ε, a}
rinf
22-10-2007, 15:40
Wenn man den ursprünglichen NEA betrachtet, führt
das erste a z.b. in den Zustand q1, welcher ein
Endzustand ist, und die nächsten a lassen den Zustand
unverändert. d.h. aaa wird sehr wohl akzeptiert, mmn.
tonico
22-10-2007, 15:56
Wenn man den ursprünglichen NEA betrachtet, führt
das erste a z.b. in den Zustand q1, welcher ein
Endzustand ist, und die nächsten a lassen den Zustand
unverändert. d.h. aaa wird sehr wohl akzeptiert, mmn.

Wenn man in einem NEA mit einem Wort in einen nicht-definierten Zustand kommt, dann akzeptiert der Automat dieses Wort nicht, denke ich. Sonst könnte man bei einem NEA die Pfeile die bei manchen Knoten auf sich selbst zeigen ja weglassen, so wie im Beispiel 2.4 der Knoten q.
rinf
22-10-2007, 16:17
Wenn man in einem NEA mit einem Wort in einen nicht-definierten Zustand kommt, dann akzeptiert der Automat dieses Wort nicht, denke ich. Sonst könnte man bei einem NEA die Pfeile die bei manchen Knoten auf sich selbst zeigen ja weglassen, so wie im Beispiel 2.4 der Knoten q.

Hab leider keine Definition dazu gefunden :-/
tonico
22-10-2007, 16:24
Hab leider keine Definition dazu gefunden :-/

Wenn man den NEA in einen äquivalenten DEA umbaut, dann akzeptiert er die selbe Sprache. Wenn man sich den minimalen DEA von MrGoatee im ersten Posting ansieht kann man leicht sehen, dass dieser DEA "aaa" nicht akzeptiert. Würde jetzt der ursprünglich Automat "aaa" akzeptieren, dann wäre der Automat von MrGoatee falsch. Ich krieg den selben Automaten raus, also nehme ich an dass meine Vermutung stimmt.
rinf
22-10-2007, 16:32
Wenn man den NEA in einen äquivalenten DEA umbaut, dann akzeptiert er die selbe Sprache. Wenn man sich den minimalen DEA von MrGoatee im ersten Posting ansieht kann man leicht sehen, dass dieser DEA "aaa" nicht akzeptiert. Würde jetzt der ursprünglich Automat "aaa" akzeptieren, dann wäre der Automat von MrGoatee falsch. Ich krieg den selben Automaten raus, also nehme ich an dass meine Vermutung stimmt.


Und zwar was passiert, wenn der Automat in einem Zustand ist, von dem es keinen Übergang für ein bestimmtes Zeichen gibt, und dieses Zeichen auftritt.
2 Möglichkeiten:
- Automat akzeptiert Wort nicht
- Zustand bleibt unverändert.

Weiß jemand die richtige Antwort?
marioana
22-10-2007, 17:10
{q1,q2} {} {q1,q2,q4}


hi!

wie kommst du auf das? ich komme hier immer auf
{q1,q2}| {} {q1,q3,q4}

auf das q2 komm ich einfach nicht?!!?

ist mein vorgehen etwa falsch?

1) ich zeichne zuerst lt. tabelle in angabe den NEA
2) ich mache die tabelle für den DEA (wie du)
3) ich zeichne den DEA
da habe ich:
(q0) ----a--->((q1,2))<------a,b----->((q4,1,3))
4) ich minimiere den DEA (da bin ich gerade dabei)
5) ich finde die dazugehörige akzeptierte sprache (in regulärer mengendarstellung?)

stimmt das so??
thoreon
22-10-2007, 20:55
@marioana:

Sorry, Tippfehler - ich hab natürlich auch {q1,q3,q4}
--> habs im obrigen Post schon korrigiert

Sorry und lg
Thomas
marioana
23-10-2007, 10:50
@marioana:

Sorry, Tippfehler - ich hab natürlich auch {q1,q3,q4}
--> habs im obrigen Post schon korrigiert

Sorry und lg
Thomas

ist kein problem - dann habe ich zum glück das gleiche wie du :)

hast du meine vorgehensweise betrachtet? stimmt die soweit?
thoreon
23-10-2007, 21:17
Hi,

NEA gezeichnet hab ich nicht, weil du ja direkt aus der NEA-Tabelle die DEA-Tabelle erzeugen kannst.
Ansonsten bin ich wie du vorgegangen.

Bei der Sprache hab ich einfach logisch überlegt und bin auf:
{ab}*{Epsilon,a}
gekommen.

Lg
Thomas
marioana
23-10-2007, 21:31
Hi,

NEA gezeichnet hab ich nicht, weil du ja direkt aus der NEA-Tabelle die DEA-Tabelle erzeugen kannst.
Ansonsten bin ich wie du vorgegangen.

Bei der Sprache hab ich einfach logisch überlegt und bin auf:
{ab}*{Epsilon,a}
gekommen.

Lg

hast du den selben automaten wie ich oben herausbekommen?

ich kann mir unter der sprache, die du angegeben hast nicht viel vorstellen - wie begründest du das? falls du einen anderen automaten hast, ists schon klar....
thoreon
23-10-2007, 21:39
Hi, ja ich denke schon, dass ich den gleichen Automaten habe wie du.
Da du die gleiche Übergangsfunktionsmatrix hast, wie ich - sollte es der selbe Automat sein.

Und in Sachen sprache habe ich mir überlegt, dass du mit {ab}* eigentlich alle ab-Kombinationen (inkl. Leerwort) darstellen kannst. Das {epsilon, a} brauchst du, damit du auch nur a darstellen kannst.

Lg
Thomas
rinf
23-10-2007, 22:24
minimieren?

Wenn ich den Algorithmus aus dem Skript anwende, bekomme ich eine leere Tabelle, d.h. dass ich jeden Zustand mit jedem zusammenfassen kann, oder?
Wie soll man das verstehen, bzw. wie komme ich dann auf den minimierten Automaten?!
marioana
23-10-2007, 22:25
Hi, ja ich denke schon, dass ich den gleichen Automaten habe wie du.
Da du die gleiche Übergangsfunktionsmatrix hast, wie ich - sollte es der selbe Automat sein.

Und in Sachen sprache habe ich mir überlegt, dass du mit {ab}* eigentlich alle ab-Kombinationen (inkl. Leerwort) darstellen kannst. Das {epsilon, a} brauchst du, damit du auch nur a darstellen kannst.

Lg
Thomas


ja schon aber in {ab}* ist ja {epsilon a} schon drinnen.
und ich habe oben den automaten angegeben: schon minimiert, aber nicht nach algorithmus sondern von mir mittels überlegung

hier nochmals:
(q0) ----a--->((q1,2))<------a,b----->((q4,1,3))

der pfeil von q1,2 und q4,1,3 geht jeweils hin und ein anderer zurück - ich kann das aber hier nur als doppelpfleil darstellen
thoreon
23-10-2007, 23:18
Nein, Das einzige Symbol in dieser Menge ist "ab" und mit {ab}* kannst du bilden {Epsilon, ab, abab, ababab etc.)
--> da ist kein Beistrich zwischen a und b :-)

Deshalb brauchst du auch die 2. Menge, damit du auch nur a abbilden kannst bzw. alle Kombinationen, die mit a enden.

Lg
Thomas
UnKI2Aut
24-10-2007, 01:04
Hab mir den NEA auch mal aufgezeichnet und erhalte ebenfalls
{ab}*.{epsilon,a}
Also wird das denk ich schon stimmen, da auch mein DEA diese Sprache ergibt!
Gedor@
24-10-2007, 01:34
Kann mir jemand von euch verraten wir ihr die Miniminierung mit mehr als einem Endzustand durchgeführt habt?
Lynx
24-10-2007, 02:56
Über Minimierung empfehle ich traditionellerweise diesen Post von Robert Craven (http://www.informatik-forum.at/showpost.php?p=212224&postcount=5), in dem der im Skriptum beschriebene Algorithmus dazu ausführlich erklärt ist.

Allerdings möchte ich zur Sicherheit noch betonen, dass das seit letztem Semester nicht mehr Vorlesungsstoff ist. Es ist nur noch der Vollständigkeit halber noch im Skriptum, und weil es eigentlich keinen Grund gab, es rauszunehmen (damit die, die es interessiert, es noch nachlesen können - alle anderen können es einfach ignorieren).
axestr
24-10-2007, 10:44
Hab mir den NEA auch mal aufgezeichnet und erhalte ebenfalls
{ab}*.{epsilon,a}
Also wird das denk ich schon stimmen, da auch mein DEA diese Sprache ergibt!

Bei {ab}*.{epsilon,a} ist ab.ab = abab enthalten. Das kann ich mit dem NEA nicht bilden.

Ich habe als Sprache Epsilon u {a} u {ab}{a}*, und als minimalen DEA
(({q0}))-a->(({q1,q2,}))-b->(({q1,q3,q4}))=a
Also DEA=< Q, {a,b}, d', F > mit Q={ {}, {q0}, {q1,q2}, {q1,q3,q4} }, F=Q-{{}} und d'
d'( {q0} , a ) = {q1,q2}
d'( {q1,q2} , b ) = {q1,q3,q4}
d'( {q1,q3,q4} , a ) = {q1,q3,q4}
d' = {} sonnst

Lg, Axel.
Teak
24-10-2007, 14:42
Bei {ab}*.{epsilon,a} ist ab.ab = abab enthalten. Das kann ich mit dem NEA nicht bilden.

Ich habe als Sprache Epsilon u {a} u {ab}{a}*, und als minimalen DEA
(({q0}))-a->(({q1,q2,}))-b->(({q1,q3,q4}))=a
Also DEA=< Q, {a,b}, d', F > mit Q={ {}, {q0}, {q1,q2}, {q1,q3,q4} }, F=Q-{{}} und d'
d'( {q0} , a ) = {q1,q2}
d'( {q1,q2} , b ) = {q1,q3,q4}
d'( {q1,q3,q4} , a ) = {q1,q3,q4}
d' = {} sonnst

Lg, Axel.

Imho kann man abab auch mit dem NEA bilden: q0, q1, q4 sind endzustände. Von q0 nach q2 mit a, dann weiter mit b nach q4, zurück zu q2 mit a und wieder nach q4 mit b. Da q4 ein endzustand ist, ergibt das abab. Aber möglich dass ich da was falsch verstanden hab,...

Lg, Jan
axestr
24-10-2007, 16:16
Imho kann man abab auch mit dem NEA bilden: q0, q1, q4 sind endzustände. Von q0 nach q2 mit a, dann weiter mit b nach q4, zurück zu q2 mit a und wieder nach q4 mit b. Da q4 ein endzustand ist, ergibt das abab. Aber möglich dass ich da was falsch verstanden hab,...

Sorry, du hast natürlich recht, ich habe gerade gesehen dass ich den NEA falsch aufgezeichnet habe ;-(

Lg, Axel.