Pumping Lemma - Fakultät < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:22 So 30.10.2011 | | Autor: | msg08 |
| Aufgabe | [mm] L_{fact} [/mm] = { [mm] a^{m!} [/mm] | m [mm] \ge [/mm] 3 } ist Sprache keines endl. Automaten
Du wählst ein n,
ich wähle w = [mm] a^{n!} [/mm] (garantiert |w| [mm] \ge [/mm] n)
du zerlegst w = [mm] a^{n!} [/mm] als uzv mit |uz| [mm] \le [/mm] n, |z| [mm] \ge [/mm] 1
dann ist uv [mm] \not\in [/mm] L_fact, denn:
sei |z|=j [mm] \le [/mm] n dann ist |uv| = n!-j > (n-1)! falls n [mm] \ge [/mm] 3.
Es gibt daher keinen endlichen Automaten A mit [mm] L_{fact}=L(A) [/mm] |
Also, meine Frage bezieht sich auf folgenden Sachverhalt. Warum darf ich bei meinem gewählten w = [mm] a^{n!} [/mm] behaupten, dass wenn ich erste n Zeichen von w nehme, sich da bereits ein Zyklus z befindet? Würde ich also zum Beispiel für m = 3 = n wählen, hätte ich ja erstmal das Wort w = [mm] a^{3!} [/mm] = [mm] a^{6} [/mm] und es gelte |uz| = [mm] a^{3}. [/mm] Für z gilt ja wegen "|uz| [mm] \le [/mm] n, |z| [mm] \ge [/mm] 1" z = [mm] a^{1}, a^{2} [/mm] oder [mm] a^{3}. [/mm] Die Aussage ist ja also, dass ich quasi einen Automaten mit 3 Zuständen habe, und dass ich eben bei einem Wort der Länge 3 auf jeden Fall einen Zyklus habe. Aber, warum darf ich es so behaupten. Also ich komm hier echt nicht weiter. Wenn ich mir jetzt zum Beispiel sagte, n ist Menge meiner Zustände und ich wähle mir ein w mit solchem n, also w = [mm] a^{n!}, [/mm] versteh ich es ja auch. Die Zerlegung würde halt dann so mit z aufgehen. Muss ich da was anders lesen, oder muss ich nun wirklich von so einem n = "Anzahl Zustände" ausgehen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:23 Di 01.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
