Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Beziehung zu |z| >= n

0 Punkte
59 Aufrufe

wenn wir in z jetzt bei kontextfreien Sprachen z.b. kein Mal durch die Schleife laufen, was ja genau dem i = 0 entsprechen müsste, dann habe ich doch nicht mehr mit Sicherheit gegeben, dass |z| >= n ist. Damit wäre dann doch auch die Grundlage der Eigenschaften für die Argumentation des PPLs hinfällig, oder nicht?

Wie wäre das dann analog bei dem PPL der regulären Sprachen zu verstehen?

 

Die Frage bezieht sich auf diesen Beitrag: https://info2.aifb.kit.edu/qa/index.php?qa=5207&qa_1=pumpen-mit-i-0

bezieht sich auf eine Antwort auf: Pumpen mit i=0
Gefragt 7 Feb in PUM-AF von uzmzu uzmzu Lernwillige(r) (260 Punkte)  
Bearbeitet 7 Feb von uzmzu uzmzu

Eine Antwort

+1 Punkt
 
Beste Antwort
Hallo,

das muss auch nicht gelten für i=0, wie du ja schon geschrieben hast, die Schleifen müssen nicht durchlaufen werden.

Die Sprache muss Pumpstellen haben (sonst könnte man nur endlich viele Wörter erzeugen).

Die Idee dahinter ist eine andere: Du nimmst ein Wort z, das mindestens n Zeichen lang ist. Dies ist die Vorraussetzung.
Dein gewähltes Wort z beinhaltet also auch eine Pumpstelle, sonst wäre es nicht mindestens n Zeichen lang. Die Schleife muss aber nicht zwangsläufig durchlaufen werden (i=0), dann ist das modifizierte Wort möglicherweiße kürzer als n Zeichen, aber es muss immer noch zur Sprache gehören, da man die Pumpstelle (von z) beliebig oft pumpen kann (i=0,1,2,...).
Also ist die Grundlage nicht hinfällig, da immer noch gilt |z| >= n.

Das selbe Prinzip gilt auch bei dem PPL für reguläre Sprachen.

Ich hoffe es ist nun klarer, wenn du noch Fragen hast kannst du gerne noch einmal schreiben.

Viele Grüße
Anne (Tutor)
Beantwortet 7 Feb von uvlwv uvlwv Eins-Komma-Null-Anwärter(in) (3,300 Punkte)  
ausgewählt 9 Feb von uzmzu uzmzu
...