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 turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant 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 huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

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