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 endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort 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 entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

2 Pluspunkte 0 Minuspunkte
115 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 :)
...