Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in PUM-AM

Beantwortet: kontextfreie Sprache, falls i>j ?

Tue, 18 Nov 2014 10:54:54 +0000

Hallo,

nein, dann wäre es immer noch keine Kontextfreie Sprache. Wähle dazu z.B. w=a^(n+1) b^n c^(n+1).

Hier die Kurzform anhand der Zerlegungen:

1)vwx enthält ein a:

Dann enthält es kein c und durch Pumpen habe ich mehr (weniger) a's als c's.

2)vwx enthält kein a:

Dann enthält es b's oder c's und ich wähle meine Pumpvariable groß genug, sodass es mehr b's und c's als a's gibt.

Gruß,

Adam (Tutor)

Beantwortet: selbe Argumentation wie bei Aufgabe 57?

Tue, 18 Nov 2014 10:53:17 +0000

Die Argumentation in den beiden Aufgaben ist schon sehr ähnlich. Allerdings darfst du nur daraus, dass wir das gleiche Beispielwort benutzen, nicht schließen, dass die Argumentation genau gleich sein muss. Es geht ja darum, in den folgenden Fallunterscheidungen das i jeweils so zu wählen, dass das dabei entstehende Wort nicht mehr Teil der jeweiligen Sprache ist. Und das kann ja in beiden Fällen unterschiedlich sein.

Beispielsweise musst du in dem Fall, dass vx kein a enthält in Aufgabe 57 das i = 0 wählen, während du in Aufgabe 58 das i > 1 wählst.

Viele Grüße

Lukas (Tutor)