pumping lemma < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:08 Fr 12.01.2007 | | Autor: | AriR |
Hey leute,
ich beschäftige mich gerade mit dem pumping lemma und ich denke ich habe den beweis einigermaßen nachvollzogen. Die anwendung dieses Lemmas ist glaub ich auch hauptsächlich nur dafür gedacht zu zeigen, dass manchen sprachen nicht regulär sind bzw. nicht kontextfrei.
Was ich jedoch nicht verstehe ist folgendes:
Wenn man sich nur die Aussage des Satzes anguckt, ohne auf den Beweis zu schauen und dann versucht zu zeigen, dass eine sprache nich kontextfrei ist zB, dann nimmt man ja meist das n, welches man auch in dem beweis des lemmas benutzt hat, nämlich das n, welches die anzahl der variablen präsentiert und sucht sich weiterhin ein wort aus, dass die voraussetzung des lemmas weiterhhin verlangt und führt das dann meist irgendwie zum wiederspruch.
soweit ist das ja alles ok, nur wennn man sich nur die aussage des satze anguckt, kann das ja sein, dass man das falsche n gewählt hat und die aussage des lemmas erst für größere n gilt (auch wenn dies unsinnig erscheint). In dem Lemma steht ja nicht dies und das gilt für das n, welches die anzahl der variablen präsentiert.
Ich hoffe ihr versteht was ich meine und könnt mir weiterhelfen.
Gruß Ari
|
|
| |
|
Moin Ari,
Du nimmst aber nicht nur das n, sondern insbesondere ein ganz bestimmtes Wort der Länge n, das Du Dir aufgrund der
Definition der Sprache, deren Nicht-Kontextfreiheit Du begründen möchtest, konstruierst.
Allgemein kann man Deine Frage nicht beantworten. Wir können es gerne anhand eines von Dir vorzuschlagenden
Beispiels diskutieren , aber nach dem Mittagessen !
Gruss,
Mathias
|
|
|
|
