+- FB18.de - Das Informatikforum ( /mybb )
+-- Forum: Diplom Informatik ( /forumdisplay.php?fid=114 )
+--- Forum: Unterbereich Grundstudium ( /forumdisplay.php?fid=123 )
+---- Forum: Formale Informatik ( /forumdisplay.php?fid=16 )
+---- Thema: Kellerautomat ??? ( /showthread.php?tid=7379 )
Kellerautomat ??? - nitro-kuh - 15.07.2004 20:15
Hallo,
kann mir jemand ganz grob und doof erklären wie ein Kellerautomat überhaupt funkioniert, so in wenigen Wörter, oder ein Beispiel geht auch, ich komme irgendwie im Skript bei dem Thema nicht mehr weiter..
Kommst das überhaupt in der Klausur ??
mfg.
nitro-kuh
Re: Kellerautomat ??? - UncleOwen - 15.07.2004 20:24
Zitat:
Kommst das überhaupt in der Klausur ??
Nein, ganz bestimmt nicht. Klausuren sind generell nur über den Stoff der ersten Semesterwoche.
Re: Kellerautomat ??? - asdf - 15.07.2004 20:34
Zitat:
Zitat:
Kommst das überhaupt in der Klausur ??
Nein, ganz bestimmt nicht. Klausuren sind generell nur über den Stoff der ersten Semesterwoche.
Ähmm, fehlt bei dir nicht ein ``
''.
Das ist wohl nicht ernstgemeint.
IIRC, kam der Kellerautomat bei uns in der Klausur vor.
Re: Kellerautomat ??? - Brokkoli - 15.07.2004 21:25
also im prinzip ist ein kellerautomat so wie ein nfa, aber er hat eben einen keller, also einen unbegrenzten geordneten speicher, in dem immer nur am oberen ende geschrieben oder gelesen werden kann.
und bei jedem zustandsübergang, wo man beim nfa eben nur ein (oder mehrere oder auch keins (lambda)) zeichen des eingabewortes liest, liest man hier nun auch aus dem keller (oder auch wieder mehrere oder keins) und schreibt danach wieder zeichen in den keller hinein (auch oben, wo man grade gelesen hatte).
d.h. ein zustandsübergang ist nur möglich wenn beim eingabewort das richtige steht und im keller das richtige steht. daher auch Z x (Sigma)* x (wasimmer)* x (wasimmer)* x Z (seite 116) für die überfühungsrelation
man befindet sich im zustand (element von Z), liest ein oder mehrere zeichen (element von (Sigma)*), liest im keller (element von (wasimmer)*) und schreibt danach in den keller (element von (wasimmer)*) und befindet sich danach in einem zweiten zustand (element von Z)
Re: Kellerautomat ??? - nitro-kuh - 15.07.2004 21:53
OK, ich versuche es nochmal das ding zu verstehen... Aber wie viel kann in der Klausur kommen?? ich meine bis Kellerautomat ist verdammt viel stoff, wie wird das alles geprüft ?? hat jemand die F1F2 Klausur schon gemacht ???
mfg
Re: Kellerautomat ??? - Brokkoli - 15.07.2004 22:05
also ich vermute mal die klausur wird so etwa zu gleichen teilen aus
- aussagenlogik
- prädikatenlogik
- dfa,nfs,reguläre sprachen usw
- kontextfreie gramatiken,pda,dpda und so
bestehen..
und weil man ja vom f2 40% schaffen muss dürfte das ganz ohne kellerautomaten so gut wie unmöglich werden ;) zumindest die grundlagen sollte man hinkriegen..
Re: Kellerautomat ??? - Cyrax - 15.07.2004 22:40
Es ist auch noch zu sagen, das es 2 Varianten des Kellerautomaten gibt bezüglich der Akzeptierung einer Sprache.
1. Im Endzustand
2. Bei leerem Keller