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 turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant 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 huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

2 Pluspunkte 0 Minuspunkte
174 Aufrufe
Habe ich das richtig verstanden?

Für jede einzelne Ableitung in meiner Grammatik muss nach dieser Aufgabenstellung gelten, dass sie ENTWEDER kontextsensitiv ODER monoton ist, denn auch mir sind hier Elemente aufgefallen, die in beiden Varianten nicht erlaubt wären.

Z.B. wie oben schonmal erwähnt die Vertauschungen von Nonterminalsymbolen als nicht kontextsensitiv und die Ableitung von S' --> lambda als nicht monoton.

Heißt das nun, dass man z.B. bei der Ableitung S'--> lambda zwar weiß, dass sie nicht monoton ist, sie aber mithilfe der kontextsensitiven "lambda-Ausnahmeregel" "aufgefangen" hat?

Danke euch für die Antwort!
in SAA-1-3 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte

Hallo,

Wie im Tutorium 3 besprochen (S.13) kannst du schon sehen, dass deine Aussage "entweder kontextsensitiv oder monoton", nicht stimmen kann, denn eine kontextsensitive Grammatik ist immer monoton, eine monotone Grammatik ist allerdings nicht immer kontextsensitiv, kann allerdings dazu umgewandelt werden.

Wie du aus den Vorlesungsfolien (Kap.4, 3. Folie) unschwer erkennen kannst, darf man auch bei monotonen Grammatiken als einzige Ausnahme S->Lambda abbilden, insofern du S nicht nocheinmal aufrufen kannst (hier wurde S' genommen, aber wie du siehst kannst du S' nicht auf S' abbilden).

Somit ist die in den Lösungen beschriebene Grammatik eine monotone Grammatik, denn (Faustregel:)"Die rechte seite ist nie kürzer als die Linke" (Vertauschungen bleiben ja gleichlang, sind also nicht kürzer). Der Ausnahmefall dass gleich zu Beginn bei S' auf Lambda abgebildet wird existiert und ist legitim.

Ich hoffe ich konnte dir weiterhelfen,

Viele Grüße,

Marc (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Danke für Ihre ausführliche Antwort. Eine Frage habe ich allerdings noch dazu: Wieso wird in AU-3 Aufgabe 3b) gesagt, dass genau diese Regel weder kontextsensitiv, noch monoton ist?
0 0
Hey,

das hat mich auch erst verwirrt, hier geht es darum dass du nur einen Ausschnitt einer Grammatik betrachtest. Du weißt also nicht ob S nicht noch irgendwo rechts steht und kannst deshalb nicht davon ausgehen, dass es das nicht tut. Und das ist ja die Voraussetzung dafür, dass die Regel (ausnahmsweise) erlaubt ist.

Hoffe das hilft noch und: viel Erfolg!
Elisabeth (Tutor)
...