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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

2 Pluspunkte 0 Minuspunkte
396 Aufrufe
Es gibt manchmal verschieden Möglichkeiten ein Wort aufzuteilen, z.B.

 

1) |vx| enthält mind ein a und kein c

2) |vx| entählt mind. ein c und kein a

 

müssen generell für den Widerspruch der dritten Regel (∀ i E No : w=xy^iz) alle Fälle bewiesen werden, oder reicht generell nur ein Besipiel bei dem es nicht funktioniert?? Genauso bei kontextrfreier Sprache.
in Allgemeine Fragen von uagll uagll Lernwillige(r) (1.1k Punkte)  
0 0
So allgemein bzw. schwammig kann man das nicht beantworten. Können Sie etwas genauer formulieren, was Sie meinen? Was ist für Sie "ein Beispiel" und was sind "alle Fälle" - und was meinen Sie mit "kontextfreier Sprache"!? :-)
1 0
Das Beispiel bezieht sich sogar auf PPL für kontextfreie Sprachen, sorry. Übungsbuch A64 (PUM-AL) und A65 (PUM-AD) sind Fallunterscheidungen zu treffen. Muss ich diese Fallunterscheidung machen, oder kann ich wenn ich zu einem dieser Fälle einen Widerspruch aufzeige, die weiteren Fälle vernachlässigen?

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Diese Fallunterscheidungen sind notwendig und essentiell! Wenn Sie einen Fall weglassen, ist das kein Beweis und Sie haben die Aufgabe nicht gelöst (Sie haben dann gerade eben nicht einen Widerspruch gezeigt!) - beachten Sie das auch für die Klausur!

Sie müssen ja für alle möglichen Zerlegungen des Testworts zeigen, dass wenn die Bedingungen (1) und (2) des PPLs gelten, dann Bedingung (3) nicht gelten kann. Sie wissen über diese Zerlegungen nur, dass sie die Struktur des Testworts haben und dass die Bedingungen (1) und (2) gelten. Wie sie exakt aussehen, wissen Sie nicht, also müssen Sie alle Möglichkeiten abdecken. Bei einfachen Aufgaben gibt es nur einen Fall, aber bei interessanteren Aufgaben können es auch zwei oder noch mehr sein.

Das PPL ist ein Beweisverfahren, und daher gibt es da wenig Raum für Schwammigkeiten (deshalb habe ich auch auf einer präzisen Formulierung der Frage bestanden). Sie können beim PPL also eher nicht mit viel Kulanz bei der Korrektur von falschen Lösungen rechnen.

von Dozent (10.1m Punkte)  
Bearbeitet von
...