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.
kontextfreie Pumpeigenschaft
Eine Frage zum Skript: im Beispiel 3.32 (a) heißt es:
L_1 = {a, ba}
Setze n_L = 4
⇒ L_1 hat die reguläre Pumpeigenschaft.
Aber warum? Wenn man v=b und w=a setzt, dann sind die ersten beiden Regeln erfüllt, aber die dritte doch nicht. Sobald i>1 sind die Wörter doch nicht mehr in der Sprache, oder?
Definition von der kontextfreien Pumpeigenschaft nochmal genau lesen:
Es kommen nur Wörter infrage mit Länge größer gleich n_L. Im Beispiel (a) gibt es keine solchen Wörter, deswegen ist die Pumpeigenschaft trivialerweise erfüllt.
In den meisten Logiken sind [m]∀x. φ(x)[/m] und [m]∀x ∈ M. φ(x)[/m] auch dann in einem Modell erfüllt, wenn die Menge, über die ∀ quantifiziert, leer ist.
(Für den Zweck von BFS lässt sich übrigens [m]∀x ∈ M. φ(x)[/m] übrigens auch als [m]∀x. (x ∈ M) ⇒ φ(x)[/m] ansehen. Selbst wenn das Universum nichtleer ist (es also Objekte für x gibt), so ist bei leerer Menge M (x ∈ M) nie erfüllt. Glücklicherweise ist in den meisten Logiken [m]φ⇒ψ[/m] jedoch auch dann erfüllt, wenn [m]φ[/m] nicht erfüllt ist, unabhängig von [m]ψ[/m]!)