|
|
Diese Aufgabe wurde von einigen als unfassbar schwer empfunden und gilt in meinem Kommiltionenkreis als allgemein unlösbar.
Aufgabe:
Obwohl Sie sich ausschließlich von Spaghetti (kurz:Ã) und Pizza (kurz: À) ernähren, achten Sie als
gesundheitsbewusster Mensch natürlich stets auf eine ausgewogene Ernährung. Sie haben sich daher
die folgenden Ernährungsregeln überlegt (für p ∈ N und s∈ N):
R1: „Für jeden Tag gilt: Entweder ich fresse Pizza oder ich esse Spaghetti.“
R2: „An höchstens p aufeinanderfolgenden Tagen fresse ich Pizza.“
R3: „An mindestens Tagen fresse ich Spaghetti.“
Um Ihr Fressverhalten zu überblicken, notieren Sie sich für jeden Tag, welche Mahlzeit Sie zu sich genommen haben. In unregelmäßigen Abständen überprüfen Sie anhand Ihrer Notizen, ob Sie Ihre Ernährungsregeln eingehalten haben.
a) Konstruieren Sie einen DFA A p über £ ={Ã,À} mit möglichst wenigen Zuständen, der beschreibt, dass Sie die Regeln R1 und R2 eingehalten haben.
b) Konstruieren Sie einen DFA A s über £ ={Ã,À} mit möglichst wenigen Zuständen, der beschreibt, dass Sie die Regeln R1 und R3 eingehalten haben.
c) Konstruieren Sie einen DFA A p,s über £ ={Ã,À} mit möglichst wenigen Zuständen, der beschreibt, dass Sie die Regeln R1, R2 und R3 eingehalten haben.
Hinweis: Konstruieren Sie einen DFA A p,s, der L(Ap)∩L(As) akzeptiert.
Die Automaten Ap und As werden durch Ap,s „gleichzeitig“ simuliert. Wie müssen die Zustandsmenge Q, die Übergangsfunktion ´ ,der Startzustand q0 und die Menge F der akzeptierenden Zustände gewählt werden?
d) Zeigen Sie: Index (L (Ap,s)) ≥p·s.
Erläutern Sie jeweils kurz Ihre Modellierung und skizzieren Sie die Zustandsdiagramme. Sie können
Teilpunkte erhalten, wenn Sie diese Aufgabe für s= 2 und p= 3 lösen.
Kommentar: Das Themengebiet "Endliche Automaten" hat im WS 17/18 zusammen mit "Kontextfreie Grammatiken" mehr als 50 % der Klausur ausgemacht. Jetzt ist der falsche Zeitpunkt nachzulassen!
Ansatz: Keiner. (Wie soll ich denn bitteschön eine DFA aufstellen, wenn weder der Startzustand bekannt ist, noch die Anzahl der möglichen Wege und deren Länge)
|
|
