Vereinfachungen - allgemein

Question

Hallo zsm :),

 

nutze das Forum hier das erste Mal :)

 

Und zwar frage ich mich im b-Teil, ob ich die Regelmenge auch vereinfachter angeben kann ? Z.B. müsste ich doch im rechtslinearen Fall mein B --> 1 ableiten können und das Testwort wäre auch erfüllt oder ? Somit wären B-->=B | 1S überflüssig oder nicht ?

 

Allgemein: Muss ich die Regelmenge nur so angeben, dass sie mein Testwort bei meinem Versuch durch ableiten am Ende erreicht oder müssen alle Fälle abgedeckt werden, die vorkommen könnten, um mein Testwort zu erreichen ?:)

 

Hoffe, Sie verstehen mein Frage :)

Viele Grüße und einen schönen Feiertag wünsche ich noch :)

Answer 1

Hallo,

bei der Formulierung einer Grammatik ist es nicht das Ziel nur ein bestimmtes Testwort zu erzeugen sondern alle Wörter die in einer Sprache enthalten sind zu erzeugen.

Wenn du die Regeln B -> 0B|1S weglassen würdest könnte beispielsweise das Wort 0101101011 nicht durch die Grammatik erzeugt werden obwohl dieses Teil der angegebenen Sprache ist (Anzahl der Einsen restlos durch 3 teilbar, Anzahl Zeichen größer 0, Wort besteht nur aus 0 und 1).

Das angegebene Testwort dient lediglich zur Überprüfung einer erarbeiteten Grammatik bzw. zur Fehlererkennung.

Zu deinem zweiten Teil: Es muss nur einen Weg für jedes Wort der Sprache geben. Falls es diesen gibt, kann das Wort erzeugt werden. Weitere Wege sind redundant.

Grüße,

Lukas (Tutor)

Comments

Hallo Lukas,

erstmal danke für deine schnelle Antwort:)

Ich kann doch aber nicht alle Fälle im Kopf abarbeiten, vor allem nicht in der Kürze der Zeit unter Klausurbedingungen.
Ich hätte das Problem z.B. mit B--> 1 nur gelöst, weil es für mein Testwort gepasst hat, das Testwort von dir ist natürlich damit nicht lösbar..
Irgendeinen Rat ?

Mfg

---

Hallo,

um alle Wörter einer Sprache abzuarbeiten reicht die Klausurzeit im Allgemeinen mit Sicherheit nicht, da meist unendlich viele Wörter in einer Sprache enthalten sind.

Es geht deshalb nicht um das Durchprobieren aller Wörter sondern um das Abbilden eines grundsätzlichen Schemas.

In der Beispielsprache geht es darum, dass wir alle Wörter bestehend aus 0 und 1, die eine Länge größer 0 und eine Anzahl von Einsen die durch drei teilbar ist erzeugen sollen.
Deshalb wählen wir im Beispiel drei Nonterminalsymbole, die den Rest beim Teilen der Anzahl der Einsen durch drei angeben (S => Rest 0, A => Rest 1, B => Rest 2).
Entsprechend ergeben sich die folgenden Ableitungsmöglichkeiten pro Nonterminalsymbol:
* Schreibe eine 0 und wiederhole das Nonterminalsymbol (Rest ändert sich nicht, bspw. S -> 0S / A -> 0A / B ->0B)
* Schreibe eine 1 und schreibe das "nächste" Nonterminalsymbol oder das erste, falls die Anzahl der Einsen wieder durch drei teilbar ist (bspw. S -> 1A, A -> 1B, B -> 1S)

Zusätzlich können wir durch Ableiten des Nonterminals B auf 1 die Ableitungsfolge beenden, da die Anzahl der Einsen somit durch drei teilbar ist.
Genauso können wir durch Ableiten des Nonterminals S auf 0 die Ableitungsfolge beenden, da hier ebenfalls die Anzahl der Einsen durch drei teilbar ist.

Einen allgemeingültigen Rat kann ich dir hier leider nicht geben, da es hier hauptsächlich auf Übung und Überlegung ankommt und die Aufgaben nicht durch ein Schema gelöst werden können.

Grüße,

Lukas

---

Ich bedanke mich recht herzlich Lukas für deine Mühen und werde mich wohl solange damit auseinandersetzen müssen, bis ich diese Überlegungen in den Aufgaben anwenden kann :)