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, dassnicht 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 alsoa's und
b's
Quoted
Deine Frage ist ein wenig irrführend formuliert. Du meinst wohl eher "Wie sieht hier das passendeaus 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 duwählst?
Quoted
Also angenommenist regulär, dann gilt PL mit den 3 Regeln, und insbesondere auch für unser
.
Für alle Zerlegungengilt 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 angenommenist regulär, dann gilt PL mit den 3 Regeln, und insbesondere auch für unser
.
Für alle Zerlegungengilt 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 demnicht.
Wo kommt diesesher?
Danke.