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 sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit 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 klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

2 Pluspunkte 0 Minuspunkte
94 Aufrufe
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 :)
in AU-1-1 von uqdrx uqdrx Eins-Komma-Null-Anwärter(in) (4.3k Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
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)
von uwdll uwdll Tutor(in) (102k Punkte)  
0 0
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
1 0
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
0 0
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 :)
...