Einführung in die Theoretische Informatik

at Universität Augsburg

Join course
254
Discussion
Documents
Flashcards
Kann mir einer bitte sagen wieso der Kellerautomat von Abbildung 4.5. deterministisch ist? Wenn ich die Übergangsfunktion von Definition 4.32 verwende kommen bei mir z.B |d(qi, a, X)| + |d(qi, e, X)| + |d(qi, a, e)| + |d(qi, e, e)| = 2 i = 2, 3 nicht kleiner gleich eins
Der Kellerautomat in 4.5 ist nicht deterministisch. Die beigefügte Antwort ist aus dem Buch "Introduction to the theory of Computation by Michael Sipser".
Ah ok, danke! Im Skript steht was anderes, das aus dem Buch macht mehr Sinn...
Was waren denn hier so eure Spekulationen?
Reduktion auf H Epsilon quer
ich habs mit einer reduktion auf Etm gemacht
Hat jemand lust die kommenden Wochen täglich ab 18:30 bis open end zusammen TI zu ballern? Also gemeinsam die Probleme finden und alle möglichen Aufgaben die uns so zur Verfügung stehen durchzuarbeiten? Lösungen und Mitschriften aus diesem sowie von letztem Jahr würde ich mitbringen. Ich will die jetzt endlich bestehen...
View 11 more comments
Heute 17:30 vor der Mathe Bibliothek
Morgen auch? Da wäre ich auch mit dabei, hätte so ab 16 Uhr Zeit...
Könnte man hier zeigen das die Funktion Power(x,y) = x^y rekursiv ist und dann behaupten, dass deswegen Power3 auch rekursiv ist?
View 1 more comment
Ich hab dir mal meine Notizen hochgeladen, die ich mir zu mü-Rekursiven Funktionen zusammengestellt habe. Keine Garantie, dass alles 100% richtig ist, aber dort siehst du auch, dass es eigentlich mit 3 (oder jeder anderen Zahl direkt) auf den gleichen Aufwand rauskommen müsste.
Super, vielen Dank!
Hat hier jemand eine mögliche Lösung für?
Hat jemad eine Lösung für Aufgabe 2? bzw eine Idee wie es funktioniert?
Kann jemand die klausurergebnisse hochladen?
View 3 more comments
stimmt, nicht ganz weil die ganzen die nicht mitgeschrieben haben und für die Prüfung angemeldet waren nicht aufgelistet sind also sind noch mehr durchgefallen
Ok, hatte mich auch schon über die geringe Teilnehmerzahl gewundert.
Das hab ich schon in der Klausur nicht ganz verstanden. Entsprechend 4.13 (Blatt 9) gilt für alle regulären Sprachen R und alle kontextfreien Sprachen C: R=>C was äquivalent zur Kontraposition ¬C=>¬R ist. Annahme: Es existiert eine nicht kontextfreie Sprache L über dem gegebenen Alphabet, dann muss die Sprache (entsprechend der Kontraposition, siehe oben) ja auch zwangsweise regulär sein. Das ist doch dann aber ein Widerspruch(?). Denn jede Sprache über einem einelementigen Alphabet ist doch z.B. via DFA als regulär zu erkennen. Kann mir da jemand auf die Sprünge helfen?
Schau dir doch mal a^n | n ist eine Primzahl an ;)
No area was marked for this question
Gibts jemand der sich als gut genug einschätzt und der seine Lösung zur Klausur hier reinstellen könnte? Das wär mega!
Weiß jemand wann üblichweise die Ergebnisse veröfftlicht werden? Dachte gestern, als ich ne Mail vom studis gekommen hab schon, sie wären online, aber dann wars nur Mathe... :/
View 5 more comments
Der chilled einfach irgendwo im Urlaub nachdem er über die Hälfte der Leute mit der Klausur zerstört hat :D
Meine Vermuntung war ja gewesen, dass er selber noch an der Lösung knobelt....
Warum hat die Klausur mein Leben zerstört ?
View 1 more comment
ja, echt so... Klausur war einfach nur zum Kopfschütteln und jetzt gibt's keine Informationen, wann wie was... -.-
Es ist halt auch echt scheiße, dass man gar nicht weiß, wie man sich vorbereiten soll... für's nächste Mal...
Hey, weiß zufällig jemand ob es bei der Einsicht von TI auch die richtigen Lösungen gibt, also ob man da auch irgendwie erfährt, was nun die/eine korrekte Antwort gewesen wäre?
Oft werden Klausuren vorgerechnet. Falls das in TI nicht der Fall sein sollte, hast du zumindest die Möglichkeit, dir von jemandem vom Lehrstuhl die richtige Lösung erklären zu lassen
Fünf Klassen für die Sprache L oder ist es etwas anderes gemeint? Weil die Sprache ist nicht regulär und damit gibts unednlich viele Klassen.
Bitte auch um Erklärung, verstehe nicht was in dieser Aufgabe gefragt ist :(
Also soweit ich das verstehe, sollen das die 5 der Sprache L sein und das wären meiner meinung nach dann [e], [a], [b], [ba] & [ab]... Bin mir da aber auch nicht sicher, falls jemand weiß ob das Stimmt oder nicht wäre ich auch für eine Antwort dankbar!
Jemand eine Idee wie Delta aussehen könnt?
Q x sigma x gamma xdelta x q0 x F x N - > P(Q x gamma) x (oben, unten, 0) Man muss am Anfang mit angeben eine natürliche Zahl n, das Ergebnis ist nun eine Menge an Möglichkeiten, wobei jeweils angegeben werden muss ob nach oben, unten oder gleich bleibt
Hat jemand vll eine vollständige Mitschrift der gestrigen Fragestunde? Speziell interessant: was wurde noch nach der Pause behandelt? Danke
hier ist (b) doch wahr oder? Es ist ja die frage ob (ab)^R ein suffix ist und nicht ein prefix und 'ba' ist ja ein Suffix von (abc)^R = cba oder sehe ich das falsch?
Kann bitte jemand kurz erklären wie ich auf die 5 Ausdrücke komme? Komme da nämlich auf mehr...
Die Funktion mischt in einer Art Reißverschlussverfahren. Das heißt Shuffle(12, 34) = {1234, 1324, 3124, 3142, 3412}. Die 1 muss immer vor der 2 sein und die 3 immer vor der 4.
Wieso ist dieser Ausdruck kontextfrei? Wenn ich 0^2t und 1^3t als w habe komme ich mit odgens lemma immer darauf, dass die grammatik nicht kontextfrei ist, egal ob ich mur 0en,1en oder beides markiere und versuche zu pumpen. Eine Antwort wäre super :)
Die Grammatik: "S --> 00S111 | epsilon" generiert die Sprache :) --------------------------------------- Alternativ kannst du dir auch einen Kellerautomaten bauen, der zuerst alle 0er einliest und in den Keller schreibt und danach immer drei 1er liest und zwei 0er aus dem Keller löscht (so wie auf dem Bild)
Gibt es Themen die von der Klausur ausgeschlossen sind?
die tage wird auf der Lehrstuhl Seite etwas dazu hochgeladen soweit ich weiß. Aber viel wird wahrscheinlich nicht ausgeschlossen
Wurde hochgeladen, alles außer Kapitel 3.5 (flex) und 4.6 (yacc)
Hat jemand einen Vorschlag?
wie wärs mit a^n b^n c^n. Die Sprache ist nicht kontextfrei , mit einem zusätzlichen Zähler ist es aber möglich die Vorkommen der a mitzuzählen und am Ende gegen die c zu verrechnen. Hätte ich jetzt spontan gemeint. Wäre das so richtig?
Danke dir! :D
und warum ist die Sprache kontextfrei?
View 4 more comments
man verstehts vielleicht besser wenn man sich klar macht wie der keller automat funktionieren könnte der die Sprache 0^n 1^m 0^n 1^m entscheidt : man legt n mal 0 auf den Stack dann legt man m mal 1 auf den stack. Nun versucht man n mal 0 weg zunehmen was aber nicht geht weil die m Einsen den zugriff darauf blockieren. Was bedeutet man bei der zweiten Sequenz an Nullen nicht überprüfen ob diese korrekt ist. Zweite möglichkeit : man legt n + m mal € auf den stack und zieht dann m + n mal € wieder ab wenn der stack danach leer ist wird die eingabe akzeptiert. Problem 00 111 000 11 wird akzeptiert ist aber nicht in der sprache d.h es ist nicht möglich einen solchen Keller automaten zu bauen da die informationen die wir bräuchten für uns nicht zugänglich sind oder verloren gehen. Das ist natürlich kein beweis sondern nur intuitiv was passiert.
Super, ich habs verstanden, danke dir! :)
Vielleicht hat jemand so eine tolle Zusammenfassung wie bei DS dieses Jahr?
HI! Kann ich hierfür bitte kurz umrissen eine Erklärung haben? :^)
Man einfachsten kann man sichs mit dem Pumping Lemma klar machen. Sei x ein Element aus Sigma* mit |x| = t, dann sei w := x [0^t 1^t ]x^R nun gilt w = uvxyz nun gilt für vxy ist in der Form 0*1* weleche alle aus dem Mittleren Intervall sind. wählt man nun i = 2, dann gilt |v^2xy^2| >= 2t+2 was bedeutet dass das wort nicht mehr in der Sprache liegt. Damit währe bewiesen dass die Sprache nicht kontext frei ist. Daraus folgt ebenfalls dass die Sprache nicht Regulär ist.
Hat jemand auch Lösungsvorschläge für die Klausuren von SS16 und SS17?
No area was marked for this question
Sind das die Lösungen von den Aufgaben des SS 16 ?
No area was marked for this question
Danke! Das rettet mir die Klausur :)
Mag hier jemand seine Mitschriften von den Übungen teilen? :)
Hallo hat jemand noch das alte Skript von Prof.Vogler mit Ueb+Lsg waere nett wenn jemand es einstellen koennte,danke