Alternativer Lösungsvorschlag - Variante 5

Question

Ich habe folgenden alternativen Lösungsvorschlag:

A steht für eine 1, B für zwei 1en, C für drei 1en und D für null 1en als letzte Zeichen.

P ={

S -> 0D|1A,

A -> 0D|1B|lambda,

B -> 0D| 1C|lambda,

C -> 0D|lanbda,

D -> 0D|1A|lambda

}

Ist diese Lösung korrekt?

Answer 1

Die Lösung aus der Aufgabe ist:

$$\begin{array}{ll}S &\rightarrow 0S \ | \ 1A \ | \ 1 \ | \ 0, \\
            A &\rightarrow 0S \ | \ 1B \ | \ 1 \ | \ 0, \\
          B &\rightarrow 0S \ | \ 1C \ | \ 1 \ | \ 0, \\
         C &\rightarrow 0S \ | \ 0 \ | \ \lambda\end{array}$$

In Ihrer Lösung:

$$\begin{array}{ll}S &\rightarrow 0D \ | \ 1A, \\
            A &\rightarrow 0D \ | \ 1B \ | \ \lambda, \\
          B &\rightarrow 0D \ | \ 1C \ | \ \lambda, \\
         C &\rightarrow 0D \ | \ 1A \ | \ \lambda\\
         D &\rightarrow 0D \ | \ 1A \ | \ \lambda\\\end{array}$$

kopieren Sie sozusagen die $S$-Regel und führen sie als $D$-Regel neu ein, wobei dann auch $\lambda$ erlaubt ist. $S$ wird im ersten Schritt für immer verlassen, sodass die Regeln $A$ bis $D$ die "Hauptarbeit" machen. Ansonsten lassen Sie jeweils $\lambda$ zu, wo in der Lösung $1 | 0$ stand. Wenn ich das richtig sehe, stimmt die Lösung bis auf die Kleinigkeit, dass das leere Wort $\lambda$ nicht abgeleitet werden kann.

Hier ist Ihre Lösung im XWizard: http://www.xwizard.de:8080/Wizz?template=ID-20910

Und hier nochmal eine $\lambda$-freie Version: http://www.xwizard.de:8080/Wizz?template=ID-20920

Diese können Sie durch Klick auf "Epsilon-frei" erzeugen (Epsilon entspricht Lambda im XWizard). Da sieht man auch, dass das leere Wort nicht ableitbar ist, und wie ähnlich Ihre Lösung letztendlich zur Lösung aus dem Buch ist.

EDIT: Das leere Wort soll gar nicht abgeleitet werden können, die Lösung ist also in Ordnung.

Comments

Vielen Dank für Ihre schnelle Antwort.
Da die Sprache über w element {0,1}^+ definiert ist, enthält sie das leere Wort doch nicht oder? Damit müsste meine Lösung dann korrekt sein.

---

Sie haben absolut recht! Ich habe ungenau gelesen.

Answer 2

Hallo,

ja die Lösung sieht auch korrekt aus. Sowohl Produktion des Testwortes als auch diverse andere Fälle die man überprüfen kann sind abgedeckt. Es wird z.B. auch verhindert, dass mehr als 3 Einsen erzeugt werden können und die „kritischen Fälle“ wie das Wort „0“ oder „1“ sind auch abgedeckt.
Wenn man genau hinschaut sieht man auch, dass sich S und D zusammenfassen lassen, denn alles was D mehr liefert ist genau der Fall S --> 0|1, alles andere wird durch S bereits abgedeckt.
und auch die anderen Lambda Übergänge die du zusätzlich eingefügt hast bewirken eigentlich nichts Anderes, als dass jede Produktion ausgehend von A,B,C noch 1|0 auf der rechten Seite bekommt, wo wir dann wieder bei der Musterlösung wären.

Grüße, Sören (Tutor)