Theoretische und technische Informatik - ganz praktisch - Letzte Fragen in SAA-1-3

Wie sehen die gepumpten Wörter für i=2 aus?

Sat, 10 Feb 2018 18:23:41 +0000

Hallo,

ich bin mir unsicher, wie das gepumpte Wort z.B. für i=2 in den fünf Fällen aussieht.

Wenn im dritten Fall i=2 gewählt wird, gilt dann für das gepumpte Wort z'= a^n b^(2n+2m) c^(3n)?

Es wäre super, wenn jemand die gepumpten Wörter für i=2 in den einzelnen Fällen kurz aufschreiben könnte.

Danke im Voraus und viele Grüße!

Wie sieht das gepumpte Wort in den einzelnen Fällen für i=2 aus?

Sat, 10 Feb 2018 13:08:35 +0000

Hallo,

ich bin mir noch unsicher, wie das gepumpte Wort für die Pumpvariable i=2 in den fünf Fällen aus der Musterlösung aussieht.

Ist für den dritten Fall z.B. bei i=2 das gepumpte Wort a^n b^(2n+2m) c^(3n) richtig? Wenn nicht, wie müsste es richtig heißen?

Es würde mir helfen, wenn jemand die gepumpten Wörter für die fünf Fälle für i=2 auflisten könnte.

Danke im Voraus und viele Grüße! :-)

Grammatik angeben

Sun, 15 Jan 2017 12:21:55 +0000

Hallo,

Der Hinweis der SAA-1-3 a) ist mir leider unklar. Wie kann die Grammatik die richtige Anzahl an Zeichen erzeugen und diese unsortieren ?

Ich bedanke m ich im voraus für eine ausführliche Erklärung der Lösung

Formaler Frage bei Fallunterscheidung des PPL für kontextfreie Sprachen

Thu, 12 Jan 2017 20:06:34 +0000

Ich habe eine Frage zur Aufgabe 3.

Hier definieren wir in den 5 Fällen ja vwx= ... Müsste es hier nicht formal korrekt heißen, dass vx =..., also zB vx= a^m statt vwx= a^m in Fall 1?
In der Lösung wird behauptet, dass etwa bei vwx = a^m gelte: für i=0 lautet das gepumpte Wort: a^(k-m)b^(2k)c^(3k).
Vernachlässigen wir dabei nicht, dass w (welches nicht gepumpt und damit nicht rausgelöscht wird) ebenso Teile der a's enthalten kann, sodass die Anzahl der a's nach dem Pumpen nicht zwingend a^(k-m) wäre? Der Widerspruchsbeweis würde ja denke ich trotzdem funktionieren, da durch |vx|>=1 immer mindestens ein a (für i=0) gelöscht würde und somit das Verhältnis der a's zu den b's und c's gestört wäre..
Oder darf man trotz beliebiger Zerlegungen (bzw trotz aller möglichen Zerlegungen, die man formal überprüfen muss) davon ausgehen, dass w leer ist?

Vielen Dank für Eure Hilfe!

Zusammenhang von monotonen und kontextsensitiven Grammatiken

Tue, 22 Sep 2015 12:01:02 +0000

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!

Warum werden bei der kontextsensitiven Grammatik nicht kontextsensitive Regeln verwendet?

Tue, 22 Sep 2015 11:58:31 +0000

Bei Aufgabe 3a) ist eine kontextsensitive Grammatik gefordert, benutzt werden aber nicht kontextsensitive Regeln (z.B. AB -> BA). Wie passt das zusammen?