Binärwörter < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:50 Mo 09.05.2011 | | Autor: | Katze_91 |
| Aufgabe | Sei A ein Automat, der genau 9 verschiedene Binärwörter erkennt.
Wie viele Zustände muss A mindestens haben? Begründen Sie Ihre Antwort |
Miau :3
Bei dieser Aufgabe verstehe ich wohl den Begriff "verschiedene Binärwörter" nicht, dachte jetzt an 0000, 0001, 0010, 0011, 0100, 0101, 0110,0111, 1000 also die Binärzahlen 0-8 aber das ist ja dann ein Automat, der Speziell diese Wörter ließt, wie verallgemeiner ich das?
Bzw. hab ich zu den 9 Wörtern einen NFA konstruiert mit 20 Zuständen oO ist wohl nicht sehr optimal.
Wäre nett wenn mir jemand eine Hilfestellung geben könnte
LG
Katze
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:13 Mo 09.05.2011 | | Autor: | felixf |
Miau!
> Sei A ein Automat, der genau 9 verschiedene Binärwörter
> erkennt.
> Wie viele Zustände muss A mindestens haben? Begründen
> Sie Ihre Antwort
Ist hier nach DFA oder NFA gefragt?
> Bei dieser Aufgabe verstehe ich wohl den Begriff
> "verschiedene Binärwörter" nicht, dachte jetzt an 0000,
> 0001, 0010, 0011, 0100, 0101, 0110,0111, 1000 also die
> Binärzahlen 0-8 aber das ist ja dann ein Automat, der
> Speziell diese Wörter ließt, wie verallgemeiner ich das?
> Bzw. hab ich zu den 9 Wörtern einen NFA konstruiert mit
> 20 Zuständen oO ist wohl nicht sehr optimal.
Fuer die Woerter kann man recht einfach einen "echten" DFA finden (damit meine ich: in wirklich jedem Zustand ist ein eindeutiger Nachfolgezustand definiert, fuer jede beliebige Eingabe) mit 9 Zustaenden.
Das liegt hier an der Struktur der Woerter, die der Automat erkennen soll.
Nehmen wir die Woerter [mm] $\varepsilon$, [/mm] 0, 1, 00, 01, 10, 11, 000, 001. Fuer die kann ich einen solchen DFA mit 7 Zustaenden finden.
Und nehmen wir nun die Woerter [mm] $\varepsilon$, [/mm] 000, 001, 010, 011, 100, 101, 110, 111. Ich kann hier einen DFA mit 5 Zustaenden finden.
Geht es evtl. noch mit weniger Zustaenden?
> Wäre nett wenn mir jemand eine Hilfestellung geben
> könnte
Du weisst einfach:
es gibt neun verschiedene Woerter [mm] $w_1, \dots, w_9 \in \{ 0, 1 \}^\ast$, [/mm] so dass der Automat genau dann ein Wort $w [mm] \in \{ 0, 1 \}^\ast$ [/mm] akzeptiert, wenn $w [mm] \in \{ w_1, \dots, w_9 \}$ [/mm] ist.
Mit dieser Voraussetzung musst du nun irgendwie arbeiten.
LG Felix
|
|
|
| |
|
Hi, danke für deine schnelle Antwort
ich gehe mal davon aus das ein DFA gesucht ist, bzw. der minimalautomat (ist doch ein DFA oder?)
das mit den 7 Zuständen bei deinem Beispiel habe ich hinbekommen
aber die 5 Zustände bei dem anderen bekomme ich nicht hin, irgendwie würden bei mir immer wörter raus kommen, die länger sind als 3
zum allgemeinen bin ich noch nicht gekommen
Miau :3
PS: bin jetzt dabei, dass der startzustand (ist auch endzustand) in zwei verschiedene geht und die beiden (in die der starzustand "trifft") jeweils in einen vierten gehen, mit 0 und 1 und dieser vierte geht mit 0 der 1 in den fünften zustand, der aber auch endzustand ist, und in keinen mehr reintrifft.
ist das ein DFA? ich bin unschlüssig, es gibt für jeden zustand ein Ziel, aber es ist das selbe...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Mi 11.05.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:21 Di 24.05.2011 | | Autor: | Katze_91 |
Für den Fall, dass solch eine Aufgabe wieder dran kommt und einem Studenten zum verzweifeln bringt.
1. es ist nicht nach einen DFA gefragt (man merkt das es ein NFA sein muss)
2. man zeigt die minimalität dadurch das man erst sagt wieviele Zustände man mindestens brauchen würde (logisch gesehen) und dann zeigt man durch ein Beispiel, dass diese Anzahl von Zuständen ausreicht
miau :3
|
|
|
|
