determ. endl. autom. < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Entwickeln sie einen DEA/DFA der die folgende Sprache über dem Alphabet {0,1} akzeptiert:
Die Menge aller Zeichenfolgen, deren 10. Symbol, links vom Ende eine 1 ist. |
ich hab da jetzt n bisschen rumprobiert, und nach nem bisschen tüfteln, bin ich zu dem schluss gekommen, dass ich ja eine extrem hohe anzahl verschiedener akzeptierender zustände habe, die sich kaum auf ein blatt bringen lassen.
anfangs dachte ich erstmal 1 und dann 9 mal egal was kommt, 1 oder 0
aber es ist ja schon wichtig, wenn ich in nem akzeptierenden Zustand bin, und dann noch eine eingabe kommt, in WELCHEM dieser akzeptierenden zustände ich bin. bsp:
[mm] q_{x} [/mm] = 1000000000 ist akzeptiert
[mm] q_{y} [/mm] = 1100000000 ist akzeptiert
[mm] q_{z} [/mm] = 1000000001 ist akzeptiert
[mm] q_{x} [/mm] udn [mm] q_{y} [/mm] unterscheiden sich jedoch, darin, dass wenn ich noch eine 0 hinten anfüge, dann wechselt der automat von [mm] q_{x} [/mm] auf einen nichtakzeptierten zustand, in dem fall [mm] q_{0}, [/mm] da nur 0000000000 der selbe zustand ist, wie keine eingabe
von [mm] q_{y} [/mm] jedoch wechselt er bei eingabe von 0 in den akzeptierenden zustand [mm] q_{x}, [/mm] bei eingabe von 1 in [mm] q_{z}.
[/mm]
sehe ich das also richtig, dass ich eine UNMENGE von akzeptierenden Zuständen habe? dürften doch sowas wie 512 verschiedene akzeptierende zustände sein ...
|
|
| |
|
Hallo JROppenheimer!
> Entwickeln sie einen DEA/DFA der die folgende Sprache über
> dem Alphabet {0,1} akzeptiert:
>
> Die Menge aller Zeichenfolgen, deren 10. Symbol, links vom
> Ende eine 1 ist.
Ich sehe dein Problem nicht so ganz. Du kannst doch von einem Zustand ausgehend nur die Möglichkeit 1 geben, und dann neunmal hintereinander Pfeile zu neuen Zuständen, die jeweils 0 und 1 enthalten, dadurch erhältst du doch alle Möglichkeiten, was hinter der besagten 1 steht. Und der allerletzte von dem ganzen ist dann der Endzustand. Mehr Endzustände brauchst du nicht.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:49 So 06.05.2007 | | Autor: | Ankh |
Und was ist, wenn zuerst beliebig viele Nullen und Einsen kommen, dann eine 1 und dann noch neun weitere Ziffern?
|
|
|
| |
|
Hallo Ankh!
> Und was ist, wenn zuerst beliebig viele Nullen und Einsen
> kommen, dann eine 1 und dann noch neun weitere Ziffern?
Was soll dann sein? Das ist doch genau die Aufgabenstellung!? ![[haee]](/images/smileys/haee.gif "[haee]")
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:36 So 06.05.2007 | | Autor: | Ankh |
Ich wollte dich nur darauf aufmerksam machen, dass deine Lösung zu einfach ist, weil du davon ausgehst, dass die Eins ganz am Anfang steht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:48 Mo 07.05.2007 | | Autor: | Bastiane |
Hallo Ankh!
> Ich wollte dich nur darauf aufmerksam machen, dass deine
> Lösung zu einfach ist, weil du davon ausgehst, dass die
> Eins ganz am Anfang steht.
Nein, davon bin ich nicht ausgegangen. Der Zustand, den ich beschrieb, sollte ein Zustand "mitten drin" sein, von Anfangszustand hatte ich da nichts geschrieben!
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:07 Di 08.05.2007 | | Autor: | Ankh |
Deine Lösung funktioniert aber nicht bei allen Wörtern der Länge > 10, die mit 1 anfangen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:58 Di 08.05.2007 | | Autor: | Bastiane |
Hallo Ankh!
> Deine Lösung funktioniert aber nicht bei allen Wörtern der
> Länge > 10, die mit 1 anfangen.
Hä - wieso das denn nicht? Über den Anfang hab' ich doch gar nichts gesagt!???
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:22 Di 08.05.2007 | | Autor: | Ankh |
Was ist denn z.B. mit dem Wort 0010 0000 0000? Das zehntletzte Zeichen ist eine 1, d.h. es sollte akzeptiert werden. So wie ich deine Lösung verstehe, wird das Wort nicht akzeptiert, da sie im ersten Zustand nach einer 1 fragt, und falls stattdessen eine 0 kommt, nicht akzeptiert.
Angenommen, dein Automat bleibt im ersten Zustand, wenn eine 0 gelesen wird (das hast du nicht genau spezifiziert), und geht weiter in den zweiten bei einer 1, dann wird das Wort 1110 0000 0000 nicht erkannt. Es sei denn im letzten Zustand (Endzustand) ist jede beliebige Eingabe erlaubt, wodurch wiederum fälschlicherweise auch 1000 0000 0000 akzeptiert werden würde.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:40 Mi 09.05.2007 | | Autor: | Bastiane |
Hallo Ankh!
Wie wär's eigentlich mal mit einer Begrüßung???
> Was ist denn z.B. mit dem Wort 0010 0000 0000? Das
> zehntletzte Zeichen ist eine 1, d.h. es sollte akzeptiert
> werden. So wie ich deine Lösung verstehe, wird das Wort
> nicht akzeptiert, da sie im ersten Zustand nach einer 1
> fragt, und falls stattdessen eine 0 kommt, nicht
> akzeptiert.
>
> Angenommen, dein Automat bleibt im ersten Zustand, wenn
> eine 0 gelesen wird (das hast du nicht genau spezifiziert),
> und geht weiter in den zweiten bei einer 1, dann wird das
> Wort 1110 0000 0000 nicht erkannt. Es sei denn im letzten
> Zustand (Endzustand) ist jede beliebige Eingabe erlaubt,
> wodurch wiederum fälschlicherweise auch 1000 0000 0000
> akzeptiert werden würde.
Also nochmal: über die ersten Zustände habe ich überhaupt nichts gesagt. Ich habe lediglich gesagt, wie das Ende des Automaten aussieht!!!
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:38 Sa 12.05.2007 | | Autor: | Ankh |
> Also nochmal: über die ersten Zustände habe ich überhaupt
> nichts gesagt. Ich habe lediglich gesagt, wie das Ende des
> Automaten aussieht!!!
Dann sag doch mal bitte, wie die ersten Zustände aussehen sollen, sonst kann man schlecht entscheiden, wie brauchbar dein Ansatz ist.
|
|
|
| |
|
ich dachte mir das auch erst so. aber wenn ich jetzt hergehe und im letzten zustand bin. von da aus müssen doch auch 1 und 0 abgehen. WO gehn die dann hin? DAS ist nämlichd ann abhängig davon, was NACH der 1 an der 10. Stelle von links kommt ... jeh nachdem, was nach dieser besagten 1 kommt sind das nämlich zwei verschiedene endzustände, von denen dann jeweils 0 oder 1 zu wieder anderen zuständen führt
|
|
|
| |
|
Hallo JROppenheimer!
> ich dachte mir das auch erst so. aber wenn ich jetzt
> hergehe und im letzten zustand bin. von da aus müssen doch
> auch 1 und 0 abgehen. WO gehn die dann hin? DAS ist
> nämlichd ann abhängig davon, was NACH der 1 an der 10.
> Stelle von links kommt ... jeh nachdem, was nach dieser
> besagten 1 kommt sind das nämlich zwei verschiedene
> endzustände, von denen dann jeweils 0 oder 1 zu wieder
> anderen zuständen führt
Wieso müssen vom letzten Zustand noch Pfeile weg gehen? Dann hättest du ja [mm] \omega-Wörter, [/mm] und dann gäbe es kein zehntletztes Zeichen!? ![[kopfkratz]](/images/smileys/kopfkratz.gif "[kopfkratz]")
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:40 So 06.05.2007 | | Autor: | Ankh |
Ein Wort kann doch auch aus elf, zwölf oder mehr Zeichen bestehen.
|
|
|
| |
|
es kann ja sein, dass die aufgabe einfach "falsch" formuliert ist.
aber es heisst ja "einen DEA, der die folgende Sprache versteht: Alle zeichenreihen, an deren 10. Stelle links vom Ende eine 1 steht."
das bedeutet: erst worte ab 10 stellen werden akzeptiert. wenn aber nach der 10. stelle noch etwas kommt, muss der das auch verstehen können, bzw. akzeptieren oder nicht akzeptieren. und das wiederrum ist abhängig davon, was die 9. Stelle links vom Ende ist ... wird die Problematik immernoch nicht klar?!
Nachtrag:
Nachdem ich jetzt meinen Prof genervt habe, und daraufhin die Mitschrift durchforstet habe, habe ich die nötige Stelle im Skript gefunden
ein NFA der die Spache [mm] L_{4} [/mm] = [mm] {0,1}^{*} [/mm] * {1} * [mm] {0,1}^{3} [/mm] akzeptiert wird in einen DFA umgewandelt der die selbe Sprache akzeptiert. Dabei hat der NFA 5, der DFA aber 16 Zustände - das wäre bei meinem Problem analog 512 Zustände!
Und dann folgt der Satz über die Minimierung von Zuständen:
Für alle n [mm] \ge [/mm] 1 gilt: Die Sprache [mm] L_{n}= {0,1}^{*} [/mm] * {1} * [mm] {0,1}^{n-1} [/mm] kann von einem NFA mit (n+1) Zuständen akzeptiert werden. Dann folg für jeden DFA mit der mit der Sprache [mm] L_{n} [/mm] = T(M) [mm] \Rightarrow [/mm] |Q| [mm] \ge 2^{n}.
[/mm]
Wenn ihr wollt, quäle ich auch den Beweis hier rein, aber dass es so ist, sollte reichen...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:52 So 06.05.2007 | | Autor: | Ankh |
Ich hab die Aufgabe schon verstanden, weiß aber jetzt auch nicht, wie man um die 512 Zustände herumkommen kann. Man kann allerdings recht einfach einen Nichtdeterministischen Automaten mit 11 Zuständen bauen und den dann per ![[]](/images/popup.gif) Potenzmengenkonstruktion zu einem deterministischen machen. Ich fürchte nur, dass dass mindestens genauso komplex ist.
|
|
|
|
