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.)

c): i für jede denkbare Zerlegung z ?

+1 Punkt
22 Aufrufe
Ich habe eine Frage zu Aufgabenteil c): Muss man für jede (!) denkbare Zerlegung von z ein i finden, für das das Wort uv^(i)wx^(i)y nicht in L liegt?
Gefragt 22, Sep 2015 in HU-3-1 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte

Hallo,

das PPL besagt, dass jedes Wort (größer gleich der PPL-Konstante k) aus einer kontextfreien Sprache eine Zerlegung besitzt, die die 3 Bedingungen erfüllt

Im Umkehrschluss bedeutet das, dass das PPL nur dann nicht erfüllt ist (also das Wort nicht aus einer kontextfreien Sprache  ist), wenn ein solches Wort mit keiner Zerlegung die Bedingungen erfüllt. Deshalb müssen alle Zerlegungen überpürft werden, was am einfachsten durch die Bildung von Fällen geschieht.

Viele Grüße

Philippe (Tutor)

 

Beantwortet 22, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...