View Full Version : Beispiel 2.1
b stimmt nicht denke ich, denn ein leerwort würde schon in einen Endzustand führen, ist aber laut Spezifikation nicht enthalten.
Muss aber zugeben, dass ichs bix jetzt noch nicht geschafft hab einen Automaten mit weniger als 7 Zuständen zu machen der das berücksichtigt
[edit] Was haltet ihr hiervon? Keine Ahnung obs richtig ist, aber man kommt jedenfalls nicht direkt in einen Endzustand
http://www.ohnitsch.net/img/uni/ws08_theo_inf_2.1b.jpg
[edit]
Okay vergesst die Lösung, 111 würde demnach auch in einen Endzustand führen. Ein Zustand mehr und es würd funktionieren... ;)
[edit] So, nächster Versuch. Bins noch nicht voll durchgegangen, aber sieht richtig aus und man kommt nicht mehr mit einem Leerwort direkt in einen Endzustand.
http://www.ohnitsch.net/img/uni/ws08_theo_inf_2.1b_2.jpg
Sorry, c stimmt natürlich.
eieiei
bei b ist ja irgendwas gültig wenns |w|0 = 2n wobei n >= 0 ist ... falls n=0 dann |w|0 = 0 = 2*0 also gültig!
aber btw. bsp b war letztes semester und ich habs mit der musterlösung verglichen. es ist so
edit: hab in der angabe nachgeschaut: es ist wirklich so... 2 * 0 = | eps | = 0 = 0 = 0 = 0 = 0 ...., da wird sich nix mehr ändern
;)
okay, angabe richtig abschreiben müsst ma können.. ;)
Hatte n>0.
Ich nehme alles zurück und behaupte das Gegenteil, danke nochmal für die ganzen Lösungen, hab mir den Rest auch durchgeschaut und denk mal alles passt.
Hallo
Wie ist Die Angabe von B und C eigntlich zu verstehen?
Was ist mit W0 und W1 gemeint?
Danke
sollte aber imho alles im skriptum stehen:
|w| = die länge des wortes w
|w|0 -> |w| mit index 0 -> anzahl der elemente "0" im wort w
|w|1 -> |w| mit index 1 -> anzahl der elemente "1" im wort w
Mein Vorschlag
Bei punkt c ist es bei dir ja nicht möglich Wörter mit mehreren 1en hintereinander am Schluss zu bilden und die sind aber laut Angabe möglich, oder versteh ich das was falsch? Fehlt da nicht einfach noch, dass man mit 1 auch im vorletzten Zustand bleiben kann?
Nein das hast du richtig verstanden.
Ich werde das doch gleich mal ausbessern
Jetzt noch den letzten "Rückpfeil" mit der 0 weg, weil der ist imho sinnlos.
welcher rückpfeil :)
nein ich habs schon geändert
DanyToss
18-10-2008, 20:29
Danke für das Einscannen, hat mir denk ich doch einiges geholfen um das Beispiel mal zu verstehen!
(a) -> Bin ich fast einverstanden, aber nach längerer Überlegung:
Was passiert wenn ( Eps Eps 0 ) oder ( Eps 1 0 ) eingelesen wird, die ja beide ungültig sind, weil das Wort mit 00 enden muss, da in 0+ ja kein Eps sein darf? Das würde deine Maschine doch akzeptieren oder?
(b) -> Find ich deine Lösung sehr gut, habe nur eine ganz andere, hoffe und denke mal, dass es gerade für NDEAs mehr als eine Lösung geben kann, auch wenn meine komplizierter aussieht.
(c) -> Bin ich aufs gleiche gekommen, ausser, dass du einen Fehler hast mit dem letzten (dazugezeichnetem) 1er Pfeil, der gehört eindeutig zum Endzustand und nicht davor, weil würdest dus so lassen und ich lese (0 1 1 1 ) ein, dann könnte das durch den Pfeil in keinem Endzustand landen.
zu (c) hätte ich somit auch die Frage ob das nun erlaubt ist, weil es nichtdeterministisch ist oder ob ich quasi damit Recht hab, dass es so falsch ist.
hmm die einwände werd ich nicht zulassen... ^^
a) a muss mit 0 enden. verstehe nicht wie du auf 00 kommst
Angabe ist {0}*{1}*{0}*{0}
eps eps eps 0 = eps eps 0 = GÜLTIG
eps 1 0 = eps 1 eps 0 = GÜLTIG
c) falsch
Skriptum: "Ein nicht deterministischer Automat akzeptiert ein Wort w, wenn es irgendeinen mit w beschrifteten Pfad gibt, der vom Startzustand qo in einen Endzustand geht"
ähm, entweder ich denk verkehrt, oder die lösung zu b) von willi.m (http://www.informatik-forum.at/member.php?u=13861) ist falsch...
der automat, den du gepostet hast, akzeptiert auch wörter wie "1", "111", "11111", etc. - was aber nicht der fall sein dürfte!
eieiei
bei b ist ja irgendwas gültig wenns |w|0 = 2n wobei n >= 0 ist ... falls n=0 dann |w|0 = 0 = 2*0 also gültig!
du denkst nicht verkehrt, nur du liest auch nicht genau,
genau das ist schon besprochen worden
bei 1, 11, 111, 1111 usw ist |w|0 = 0
damn... :shiner:
tut leid!
DanyToss
19-10-2008, 02:55
Ok ... dachte das wäre 0+ in der Angabe in der vorletzten ... mit Stern passts klar :)
Gut, dann für (c) egal, aber ich würd den Pfeil trotzdem aufs letzte setzen :)
http://www.ohnitsch.net/img/uni/ws08_theo_inf_2.1b_2.jpg
und wie bekommst du lwl0=0 ??
und noch jemand ^^
die lösung die du zitiert hast war für n>0, ein fehler beim abschreiben der angabe von klesk.
andere post - andere lösung wos geht
(ein kleiner tipp: ganz oben könntest dus finden)
schrankk
20-10-2008, 22:23
schade, dass die Zustände nicht beschriftet sind, ist nicht so leicht genau zu erklären, was ich will, aber trotzdem:
bzgl. a) mMn sollten die Kanten sowohl zwischen Anfangszustand und dem zweiten Zustand, als auch die Kante zu sich selbst in zweitem Zustand mit 1, E beschriftet sein. Was meint ihr?
Silent_Bob
21-10-2008, 22:01
Hi!
a,b kann ich von willi.m nachvollziehen...
bei c, aber habe ich eine andere Lösung. Da zB: das Wort 0110111
sowohl die Form 0w1 mit w = {0,1}* sowie |w|1 >= 3 mit w={0,1}* habt,
liegt es im Durchschnitt der beiden Mengen und muß vom Automat akzeptiert werden.
Darum müste der Automat mMn so aussehen....
mfg tom
das wort 0110111 wirddoch eh von willi.m's automaten akzeptiert
Hallo
wie ist eigentlich die Angabe von (B) zu verstehen, ich verstehe von der Angabe aus, nicht was der Automat genau Akzeptieren soll?
Danke
Silent_Bob
22-10-2008, 12:14
das wort 0110111 wirddoch eh von willi.m's automaten akzeptiert
Ja stimmt, ich hab nicht bedacht daß die Nullen ja optional sind und im vorletzten Zustand {1,0}* dargestellt werden kann.
ich komm jetzt auch auf die Lösung von willi.m :thumb:
mfg tom
a solte so auch gehen, oder?
Gegenbeispiele?
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.