SS15.pdf

Exams
Uploaded by Anonymous User at 2017-07-27
Description:

Klausur mit Musterlösung

 +2
174
4
Download
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)
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! :)
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.