This post has been edited 2 times, last edit by "Skuld" (Aug 29th 2010, 11:52am)
This post has been edited 1 times, last edit by "Skuld" (Aug 29th 2010, 2:16pm)
Ach, und noch mal zur Klarstellung: Die Aufgabenstellungen "Zeigen Sie, dass die Sprache nicht von einem endlichen Automaten entschieden werden kann" und "Zeigen Sie, dass die Sprache nicht regulär ist", sind äquivalent?
Für uv²w würde dann aber gelten, dass vorne doppelt so viele a's wie hinten stehen, und solche Worte sind ja nicht in L(2).
dein Wort x darf als Variable nur noch n im Exponenten haben.
This post has been edited 1 times, last edit by "Skuld" (Aug 30th 2010, 1:05pm)
Eine Frage zu Aufgabenstellungen bei Kellerautomaten: "Geben Sie den KA an und begründen Sie seine Korrektheit!" -> d.h. für ein gültiges Beispielwort die Rechnung durchführen?
Ach und ist eine Überführung der Form z(1) # A -> z(2) gültig? D.h. ohne dass ich was aus dem Keller lösche oder etwas in ihn hineinschreibe (also praktisch das gelesene Zeichen überlese?)
Mir ist hier nicht ganz klar was Du mit "z(1) # A -> z(2)" meinst, da # i.d.R. ein Kellersymbol ist und die Übergangsfunktion als "Z x Sigma x Gamma -> Z x Gamma^*" definiert wird, wobei Z die Menge der Zustände, Sigma das Eingabe- und Gamma das Arbeitsalphabet ist.
PS: der LaTeX-Plugin scheint kaputt zu sein.
This post has been edited 1 times, last edit by "Skuld" (Aug 30th 2010, 3:51pm)
Aus der Klausur SS07.
Aufgabe 3:
Beweisen Sie, dass nicht regulär ist.
Wie sieht hier das passende x und die Zerlegung uvw aus?
Ich steh da irgendwie auf dem Schlauch und bekomme keine passende Zerlegung hin.
Danke.
Dann kannst du mit uv ein ganzes n nehmen also a's und b's
Quoted
Deine Frage ist ein wenig irrführend formuliert. Du meinst wohl eher "Wie sieht hier das passende aus und wie zeige ich für alle möglichen Zerlegungen , dass für jede es ein gibt, sodass das ?", oder?
Quoted
Wie wärs, wenn du wählst?
Quoted
Also angenommen ist regulär, dann gilt PL mit den 3 Regeln, und insbesondere auch für unser .
Für alle Zerlegungen gilt nun, dass nur aus s und mindestens einem besteht (aufgrund der Anfangslänge). D.h. wenn wir nun beispielsweise wählen, dann gilt nun: . Da jedoch ist, verletzt dies genau die Bedingung, dass alle Wörter die Form haben sollen für die Anzahl der s. Also gilt , was ein Widerspruch zur Annahme ist.
Quoted
Also angenommen ist regulär, dann gilt PL mit den 3 Regeln, und insbesondere auch für unser .
Für alle Zerlegungen gilt nun, dass nur aus s und mindestens einem besteht (aufgrund der Anfangslänge). D.h. wenn wir nun beispielsweise wählen, dann gilt nun: . Da jedoch ist, verletzt dies genau die Bedingung, dass alle Wörter die Form haben sollen für die Anzahl der s. Also gilt , was ein Widerspruch zur Annahme ist.
Ich verstehe die Stelle mit dem nicht.
Wo kommt dieses her?
Danke.