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!
 

 

alternative Zerlegung PPL für kontextfrei Sprachen A66

0 Punkte
44 Aufrufe
Hallo, ich wollte Fragen, ob auch eine alternative Zerlegung hier möglich wäre:

1. Fall vx enthält mindestens eine 0

dann enthält vx keine 2 oder 3. Entsprechend wäre bei eine i>1 die Anzahl der 0 größer als die der 2 und 3 und somit das Pumpwort nicht Teil der Sprache

2. Fall vx enthält keine 0

(1) vx enthält mind. eine 1 (2) vx enthält mind eine 2 (3) vx enthält mind eine 3

(1) für i=0 gibt es dann im Pumpwort mehr 0 als 1 entsprechend nicht Teil der Sprache

(2) für i=0 gibt es dann im Pumpwort mehr 0 als 2 entsprechend nicht Teil der Sprache

(3) für i=0 gibt es dann im Pumpwort mehr 0 als 3 entsprechend nicht Teil der Sprache

=> damit kann man einen Widerspruch feststellen

 

Wären in diesem Fall alle Zerlegungen berücksichtigt? Ich bin mir da nicht ganz sicher. Vielen Dank im Voraus
Gefragt 12 Feb in PUM-AG von Anonym  

Eine Antwort

0 Punkte
Hallo,

deine Unterscheidungen im zweiten Fall überschneiden sich: wenn $vx$ eine $1$ oder eine $3$ enthält, kann es trotzdem auch eine $2$ enthalten.

Außerdem folgt im zweiten Fall für (1) nicht direkt, dass das gepumpte Wort nicht in der Sprache liegt: Mehr $0$en als $1$en sind grundsätzlich erlaubt, solange $\vert z\vert _0=\vert z \vert _2$ und $\vert z\vert _1=\vert z \vert _3$ gilt. Das gleiche gilt auch für die anderen Fälle.

Viele Grüße

Julia (Tutorin)
Beantwortet 12 Feb von uodvo uodvo Tutor(in) (106,190 Punkte)  
...