Fachrat Informatik - Forum
FACHSPEZIFISCHE DISKUSSIONEN
Grundlagen der Informatik
Theo-Inf: Aufgaben
Thursday, August 22nd 2002, 10:29am
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Thursday, August 22nd 2002, 6:53pm
Das Verfahren aus der Vorlesung funktioniert. Eben ausprobiert. Am besten, du beschreibst mal genau deine Schritte bis zu der Stelle, an der du nicht weiterkommst.
Quoted
Original von migu
1) In der letzten Klausur musste in Aufgabe 8 der Automat minimiert werden. In der Klausur war ich an dieser Aufgabe verzweifelt, da das Verfahren, das ich kannte, nicht funktionierte. Wie minimiert man diesen Automat und geht das überhaupt?
Ich komme für die Sprache des Automaten auf den Ausdruck a^(n+1) b^(2n) mit n >= 0. Das wäre dann nur die Sprache L3.
2) Aufgabe 3 c): Nach meinen Erkenntnissen werden die Sprachen L3 und L6 erzeugt. Ist das richtig?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Thursday, August 22nd 2002, 7:13pm
Das ist glaube ich ein Fehler in der Klausurmitschrift. Ich meine, daß damals a^(2^n) gefragt war. (a^2)^n = (aa)^n wäre auch etwas arg einfach, da regulär.
Original von loki
a) L8= {(a^2)^n|n>=1}
Ist regulär.
b) L9= {(01)^n|n>=0}
Ist kontextfrei.
c) L10={a^nb^n-3|n>=3}
Friday, August 23rd 2002, 4:59pm
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Friday, August 23rd 2002, 5:37pm
Hmmm, die neuen Zustände habe ich auch so, aber einen anderen regulären Ausdruck (mit deiner Klammerung scheint etwas nicht zu stimmen):
Original von KreiS
migu : die Sprache ist a | ( ( a | (a | b ) ) b* a (a|b)*
zusammen fassen kann man s1 und s5 zu s15 und s2 und s4 zu s24, das wars.
Ich komme auch auf acht Zustände, nämlich:
hat einer aufgabe 1 richtig gelösst, das entfernen an sich sollte ich richtig haben, nur zum DFA ergeben sich bei mir 8 zustände
Friday, August 23rd 2002, 6:47pm
hatte beim ersten post nen | b unterschlagen :-( auf dem Blatts stehts wenigstesns korrekt :-)Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Friday, August 23rd 2002, 8:01pm
Bei mir fallen s0, s1 und s2 zu s0/1/2 zusammen sowie s3 und s4 zu s3/4.
Original von KreiS
also irgendwie stimmt bei 1 es wohl doch net
also s1 und s3 habe gestrichen bei e entfernung.
|
Source code |
1 2 3 4 5 6 7 |
| s0/1/5 | s2 | s3/4 | s6 | s7 | --+--------+--------+--------+--------+--------+ a | s2 | s7 | s2 | s7 | s7 | --+--------+--------+--------+--------+--------+ b | s0/1/5 | s3/4 | s3/4 | s6 | s3/4 | | s6 | s0/1/5 | | | | --+--------+--------+--------+--------+--------+ |
Friday, August 23rd 2002, 8:19pm
ist das falsch was ich einschlage?! Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Friday, August 23rd 2002, 8:37pm
Original von KreiS
s3 lässte man weg und verbindet s2 mit s4 oder man vereint sie, kommt aus selbe hinaus.
bei s0 schlage ich ne verbindung zu s1
s0 a -> s2
s0 b -> s6 oder s0
wenn ich s1 und s0 zusammen fasse stimmts ja soweit auch.aber warum s5 mit s12 dann verschmelzen lassen, das blicke ich gerade net
Kann ich gerade nicht ganz nachvollziehen, deine Beschreibung ist nicht besonders exakt.
Friday, August 23rd 2002, 9:01pm
Sunday, August 25th 2002, 11:33pm
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, August 26th 2002, 12:44am
TM rechnet mod 3 mit der zweiten Zahl, siehe http://forum.fsinf-hannover.de/thread.ph…0&boardid=16#10.
Original von Yann
Weiß einer was diese §$%&/! Turingmaschine anrichtet?
Ist ein Fehler in der Klausurmitschrift. Der dort genannte Zustandsübergang (s_0, |, s_1, #, r) müßte korrekt (s_0, | s_0, #, r) lauten. Dann macht das ganze auch wieder Sinn ...
Allerdings klapp es mit 1:3 und 2:3 nicht -> man erhält nämlich 1 bsw. 2...
Monday, August 26th 2002, 11:15am
Monday, August 26th 2002, 11:24am
Monday, August 26th 2002, 11:38am
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, August 26th 2002, 3:09pm
Kann ich bestätigen.
Original von Diktator
[Aufgabe 3]
kann jemand diese ergebnisse verifizieren?
Die Begründung finde ich etwas seltsam. Am besten, du argumentierst direkt über die Grammatik, d. h. stellst fest, daß die angegebene Grammatik linkslinear ist, es sich also bei L8 maximal um eine reguläre Sprache handelt. Zudem solltest du noch schreiben, warum L8 zu keiner kleineren Sprachklasse gehört. Das ist in diesem Fall klar: es gibt nämlich keine.
Original von Diktator
zu a)
eine mögliche grammatik wäre
S->Saa|aa.
sie erzeugt eine gerade anzahl von a's, mindestens aber zwei.
L8 gehört ferner zu regulären sprachen, da es einen endlichen automaten A gibt (drei zustände), so dass gilt L8=L(A).
Geht auch einfacher: S->S01|e
zu b)
eine grammatik ist
S->e|01|S01 mit e=leeres wort.
Solltest du IMHO anderes begründen (siehe meine Antwort zu a) )
L9 ist auch reguläre sprache, da ein endlicher automat mit drei zuständen existiert, der wörter von L8 erzeugt.
Kleiner Fehler: Mit dieser Grammatik erzeugst du ein b am Ende zuviel. Sie müßte lauten: S->aaaT, T->e|aTb
zu c)
eine grammatik ist
S->aaaTb; T->e|aTb.
Komische Begründung. Diese Grammtik ist kontextfrei, da auf der linken Seite immer nur ein Nichtterminal steht. Sie ist nicht regulär, da sie vom Typ a^kb^k ist. Und das ist bekanntlich mindestens kontextfrei.
L10 ist eine Typ-1-Sprache, da es keine kontextfreie grammatik dazu gibt. die genannte grammatik ist kontextsensitiv. folglich gibt es auch keinen kellerautomaten zu L10.
Monday, August 26th 2002, 3:32pm
