Lösungsideen bzw Tipps?
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Klausuren Teil I
Hallo zusammen, bin dabei die alten Klausuren zunächst einmal für ThI I durchzumachen. Dabei stellen sich mir die ein oder anderen Fragen. Vielleicht kann man die hier diskutieren.
Also Aufgabe I-2 F2004:
c,d)
Ich würde behaupten, dass die Sprachen L alle drei regulär sind, vorausgesetzt, dass man eben ein festes n hat. Denn dann kann ich DEA’s angeben, die diese Sprache entscheiden, wobei die Anzahl der Zustände in direktem Zusammenhang zu n steht.
L_1,n: |Q| = 2n + 1
L_2,n: |Q| = 3n + 2
L_3,n: |Q| = n^2 + 2n + 2
Allerdings frag ich mich jetzt im Bezug auf das Pumping-Lemma, ob diese Sprachen tatsächlich regulär sind. Kann es sein, dass das Lemma immer erfüllt ist, wenn man für ein p > |Q| kein Wort findet, dessen Länge größer gleich p ist? Denn bei obigen Sprachen kann p gar nicht kleiner gleich |Q| gewählt werden. Im Grunde wird bei den DEA’s zu diesen Sprachen höchstens der Fehler-Zustand (Wort zu lang, Bed. kann nicht mehr erfüllt werden) wiederholt. Dann ist aber dieses Wort nicht Element der Sprache.
Anders formuliert: Die Sprache a^nb^n (n > 0) ist nicht regulär,
ist aber a^10b^10 regulär? Denke schon, wie lässt sich das aber mit dem Pumping-Lemma vereinbaren?
Ich komme gerade zu dem Schluss, dass das Pumping-Lemma für jede Sprache erfüllt ist, deren Wörter feste gleiche Länge haben. Diese sind dann also regulär. Weil dann die linke Seite der Implikation nie erfüllt werden kann und somit die gesamte Aussage wahr ist ( a => b → nicht a oder b). (Vgl Def. des Pumping-Lemmas Übung 10 Aufgabe 34)
Außerdem ist noch M_1 regulär, das ist einfach die Sprache mit allen Wörtern gerader Länge.
Die Sprachen M_2,3 sind nicht regulär, da müsste man endlos zählen können.
F2004 I-2:
e)
M_2: gute Frage, wie müsste eine passende Grammatik aussehn?
M_3: kontextfrei ( S → €, S → aSb )
hallo, glaube mich an den spruch zu erinnern:
eine endliche sprache ist immer regulaer.
sollte auch passen, weil du da ja immer einen automaten angeben kannst.
stimmt auch
a^n b^n für festes n
machste n Zustände für a und n für b der n-te von b is Finalzustand → akzeptiert
Du kannst ja im Prinzip dann für jeden Buchstaben einen Zustandangeben und dein Automat bleibt trotzdem noch endlich