Welchen Sinn hat die Aufteilung in N0, N1, E0, E1 der Non-Terminalzeichen?

Question

Kann man bei der äquivalenten monotonen Grammatik die Non-Terminalzeichen N und E einfach beibehalten? In der Musterlösung wurden diese aufgeteilt in N0, N1, E0, E1, was ist der Sinn dahinter?

Answer 1

Hallo,

ich probiere Dir den Gedankengang der Produktionsregeln mal zu verdeutlichen. Vielleicht wird der Sinn dann klarer.

Also zuerst enthält die zweimal dieselbe Anordnung von Zeichen also kann man w folgendermaßen aufteilen: w = xx.

Der erste Teil wird dabei direkt aus A erzeugt und wird auch anschließend nicht mehr verändert.

Hier ein kleines Beispiel:

AT  -> 0ANT -> 00ANNT -> 001AENNT -> 0011AEENNT

Wenn der erste Teil, also x, vollständig erzeugt wurde, wird das A "herausgelöscht" Man erhält somit 0011EENNT.

Nun fällt auf, dass sich die hinteren Nonterminalsymbole noch in der falschen Reihenfolge befinden. Denn das Wort der Sprache, zu dem wir gelangen wollen, lautet 00110011.

Der nächste Schritt ist somit, dass wir das letzte Nonterminalsymbol (T ausgenommen) durch ein Terminalsymbol ersetzen. Anschließend bleibt uns laut den Produktionsregeln nichts anderes übrig als die erzeugte 0 mindestens einmal nach links durchlaufen zu lassen (0011EE0NT). Ab dann sind zwei grundsätzliche Produktionen möglich (Variationen gehen natürlich auch):

0011EE0NT -> 0011EE00T -> 0011E0E0T -> 0011E00ET -> 0011E001T -> 00110E01T -> 001100E1T -> 0011001ET -> 00110011T -> 00110011

oder

0011E0ENT -> 00110EENT -> 00110EE0T -> 00110E0ET -> 001100EET -> 001100E1T -> 0011001ET -> 00110011T -> 00110011

Abschließend wird dieser ganze Aufwand betrieben, um einfach abzusichern, dass im zweiten Teil die Reihenfolge wie benötigt umgedreht wird.

Sollte dies Deine Frage nicht beantwortet haben, konkretisiere sie bitte erneut.

Viele Grüße

Christoph (Tutor)

 

Comments

@Christoph Meine Frage bezieht sich eigentlich nur auf die Umformung zur monotonen Grammatik. Mir ist klar warum man dort A und T in jeweils 2 Hilfsvariablen augeteilt hat, aber nicht warum man analog dazu N und E ebenfalls aufteilt in jeweils 2 Variablen. Soll das nur der Verdeutlichung dienen?!

---

Hallo,

hmm... das ist eine gute Frage! Die Aufgabe ist nicht ganz leicht, und als wir sie vor Jahren erstellt haben, waren wir der Meinung, dass man diese Aufspaltung in N0/N1 usw. braucht. Auf den ersten Blick sehe ich im Augenblick aber auch nicht, warum. Vielleicht können Sie ja mal eine Alternativlösung entwerfen, und wir schauen dann, ob sie auch funktioniert...

Viele Grüße

Lukas König, Friederike Pfeiffer-Bohnen und Micaela Wünsche

---

Hallo zusammen, ich möchte diese Frage gerne noch einmal aufgreifen. Mein alternativer Lösungsvorschlag wäre, N und E eben nicht aufzuteilen.

Ich habe meinen Vorschlag in den xWizzard getippt, hoffe das passt so:
http://www.xwizard.de:8080/Wizz?template=ID-22139