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.)

Schöne Ferien!
 

 

Alternativer Lösungsvorschlag - Variante 5

+1 Punkt
43 Aufrufe
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?
Gefragt 12, Jan 2017 in REC-AB von uodsh uodsh Eins-Komma-Null-Anwärter(in) (2,280 Punkte)  

2 Antworten

+1 Punkt
 
Beste Antwort

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.

Beantwortet 12, Jan 2017 von Lukas König Dozent (10,064,890 Punkte)  
ausgewählt 27, Jan 2017 von uodsh uodsh
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.
0 Punkte
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)
Beantwortet 12, Jan 2017 von updrr updrr Eins-Komma-Null-Anwärter(in) (3,790 Punkte)  
...