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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 0 Minuspunkte
75 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?
in REC-AB von uodsh uodsh Eins-Komma-Null-Anwärter(in) (2.3k Punkte)  

2 Antworten

1 Pluspunkt 0 Minuspunkte
 
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.

von Dozent (10.1m Punkte)  
ausgewählt von uodsh uodsh
0 0
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.
0 0
Sie haben absolut recht! Ich habe ungenau gelesen.
0 Pluspunkte 0 Minuspunkte
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)
von updrr updrr Eins-Komma-Null-Anwärter(in) (4.7k Punkte)  
...