Theoretische und technische Informatik - ganz praktisch - Letzte Fragen in PUM-AF

alternativ

Fri, 21 Jan 2022 15:03:48 +0000

Hallo,

Kann ich als IyI => 1 und mit xy =0^j 1<=j<=n,

y=0^k 1<=k<=j zeigen ?

Beziehung zu |z| >= n

Thu, 07 Feb 2019 15:24:04 +0000

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

Zerlegung

Thu, 02 Feb 2017 10:46:56 +0000

Hallo,

in der Lösung wurde bei dieser Aufgabe folgende Zerlegung gewählt:

x = a^(j-k) y = a^k z = a^(n-j) bbc^n

Ich jedoch habe...

x = a^k y = a^j z = bbc^n gewählt.

Wenn ich dann i = 0 nehme, komme ich aber auch auf a^(n-j) bbc^n, was dann keine Typ-3-Sprache ist.

Muss ich im z eigentlich das a noch drin haben oder ist meine Lösung auch korrekt?

Gruß

PS: Wie nutze ich hier eigentlich die Formeldarstellung wenn ich einen Beitrag schreibe?

Pumpen mit i=0

Wed, 01 Feb 2017 09:57:18 +0000

Hallo,

in der Aufgabe wird $y$ mit $i=0$ also $xy^0z$ gepumpt.

Widerspricht das nicht der 2. Annahme, dass $|y| \geq 1$ sein muss?

Wo liegt da mein Denkfehler? Vielen Dank im Voraus!

Pumpinglemma

Wed, 22 Oct 2014 11:05:12 +0000

Warum wird bei dieser Aufgabe y != lamda gesetzt und nicht wie sonst immer y >= 1 ?

Vielen Dank

Fallunterscheidung

Wed, 22 Oct 2014 11:03:33 +0000

Müsste hier dann nicht auch eine Fallunterscheidung gemacht werden? Es gäbe verschiedene Möglichkeiten der Zerlegung für xy, die zwar auf dasselbe hinausführen, aber in der Musterlösung wurde ja nur der Fall betrachtet, dass xy nur aus a's besteht.

Pumpinglemma Widerspruchsbeweis

Wed, 22 Oct 2014 11:00:41 +0000

Hallo,

Ich bin bei der Aufgabe so vorgegangen das ich am Anfang auf die Gleichmächtigkeit von rechtslinearen Grammatiken und EA verwiesen habe. Und hab den Widerspruchsbeweis dann mit dem PPL für EA-Sprachen geführt. Wäre das auch korrekt?

Viele Grüße

Pumpinglemma Gegenbeispiel

Wed, 22 Oct 2014 10:57:32 +0000

Hallo:)

Muss ich denn allgemein beim PPL für Sprachen immer alle Gegenbeispiele geben oder reicht auch schon ein Gegenbeispiel aus?

Dankeschön