Ich weiß, dass dies nicht direkt mit der Programmierung zusammenhängt, aber ich habe mich gefragt, ob jemand das Pumping-Lemma auf den folgenden Beweis anwenden kann:
Zeige, dass L = {(a ^ n) (b ^ n) (c ^ m): n! = m} ist keine kontextfreie Sprache
Ich bin ziemlich zuversichtlich, wenn ich Pump-Lemmas anwende, aber dieses hier nervt mich wirklich. Was denkst du?
Edit: Ich habe dich total falsch geführt. Das passiert, wenn ich versuche zu helfen, wenn ich das Problem nicht vollständig gelöst habe.
Angenommen, L ist kontextfrei. Nach Ogdens Lemma gibt es eine Ganzzahl p mit folgenden Eigenschaften:
Wenn ein String w in L mindestens p Symbole lang ist, wobei mindestens p dieser Symbole "markiert" sind, kann w als uvxyz dargestellt werden, die erfüllen:
Das ist Ogdens Lemma. Nun sei q eine Ganzzahl, die durch jede positive ganze Zahl, die nicht größer als p ist, teilbar ist. Sei w = a p + q b p + q c p . Markiere alle c. Mit # 2 muss u oder v mindestens einen c enthalten. Wenn entweder u oder v ein anderes Symbol enthält, schlägt # 4 fehl, also müssen u und v nur c enthalten. Aber dann fällt # 4 aus, wenn i = q / | uv |. Wir wissen, dass q durch | uv | teilbar ist weil p & gt; | uv | & gt; 0, und q ist teilbar durch alle positiven ganzen Zahlen kleiner als p.
Beachte, dass Ogdens Lemma zum pumpenden Lemma wird, wenn du alle Symbole markierst.
Angenommen, L ist kontextfrei. Durch das Pumping-Lemma gibt es eine Länge p (nicht notwendigerweise das gleiche p wie oben), so dass jeder String w in L als uvxyz dargestellt werden kann, wobei
Gegeben eine Saite w in L, entweder m & gt; n oder m & lt; n. Angenommen p = 2.
Angenommen, dass m & gt; n. (Beachten Sie, dass Λ die leere Zeichenfolge bezeichnet.)
Angenommen, dass n & gt; m.
Dies zeigt, dass kein String von L ein Gegenbeispiel mit dem Pumping-Lemma liefert, um zu der Annahme zu gelangen, dass L eine kontextfreie Sprache ist (obwohl es kontextsensitiv ist).
Tags und Links theory language-theory proof automata