Dieser NFA alsDFA darstellbar? < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 21:43 Di 25.10.2011 | | Autor: | Siaaw |
| Aufgabe | Geben Sie für jede der folgenden Sprachen über dem Alphabet E = {0,1} jeweils einen DFA und NFA mit möglichst wenig Zuständen an:
L = [mm] \{w | |w| >= 2 und das zweitletzte Zeicehn von w ist eine Eins} [/mm] |
Hallo,
ich zerbreche mir den Kopf bei einer Aufgabe einen DFA und einen NFA mit möglichst wenigen Zustände anzugeben.
START-> q0 --1--> q1 --0,1--> q2
Wobei q0 den Start und q2 den Endzustand beschreibt
Meine Frage wäre, ob es einen DFA gibt bzw wie dieser aussieht, da ich schon alles versucht habe, aber nichts richtiges bei rumgekommen ist.
zB einen Übergang von q2 nach q1 mit einer 1 - dann fehlt aber noch einen Übergang von q2 nach ? mit einer 0 - das aber nicht möglich ist. Beispielsweise das Wort 1110 [mm] \in [/mm] L aber würde nicht zu meiner Überlegung passen.
Ich hoffe ich habe ich mich verständlich ausgedrueckt.
Lg
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:[http://www.informatikforum.de/showthread.php?t=189735]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Do 27.10.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
