Eine extrem schwere Aufgabe zur Modellierung von DFAs

Question

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)

Answer 1

Ich würde mal behaupten, dass ist ein Fangfrage ;-)

Denn was zeichnet den DFA und die Chomsky-Typ-3 Sprachen aus? -

Eine Menge p kann nur durch eine Menge m an Zuständen dargestellt werden. Ist kein p gegeben, dann kann kein DFA aufgestellt werden, da keine Regularien gelten.

Selbst mit einem NFA ist dies nicht möglich.

Um ein Mengenproblem zu lösen braucht man zwingen einen Speicher, der eine Menge simuliert, da dieser im FA nur durch Zustände dargestellt werden kann, ist zwingend gefordert, wie weit der FA zählen muss. Es ist nicht möglich, einen dynamischen finiten Automaten aufzustellen.

Da diese Sprache in der Grammatik Schreibweise ebenfalls die Regeln der Typ-3 Sprachen nicht erfüllt, sondern allenfalls die der Typ-2 Sprachen, ist zwingend ein PDA erforderlich, der durch den Kellerspeicher weitere Elemente speichern kann.

Man beachte zudem den Kommentar: "Kontextfreie Grammatiken seien 50%iger Bestandteil des WS". Naja, kontextfreie Sprachen können nicht mit einem DFA modelliert werden. Ich glaube der Prof wollte prüfen, ob man die endlichen Automaten wirklich verstanden hat.

Eine einfache Antwort in Form eines Satzes reicht wohl vollkommen aus. Einen DFA kann man meines Erachtens nur bilden, wenn p und s gegeben sind, das heißt die Teilpunkte kann man mit Zeichnen erreichen, die volle Punktzahl gibt's dann für Fachwissen ;-)

Beste Grüße

Answer 2

Konstruieren Sie einen DFA

Der DFA ist A_p = (Q, Σ, δ, q₀, F) mit

• Zustandsmenge Q = {q₀, ..., q_p, v},
• Übergangsfunktion δ,
• Akzeptierenden Zuständen F = {q₀, ..., q_p}.

Dabei ist

• δ(q_i, π) = q_i+1 für jedes i ∈ {0, ..., p-1}
• δ(q_p, π) = v
• δ(v, λ) = v für jedes λ ∈ Σ
• δ(q_i, σ) = q₀ für jedes i ∈ {0, ..., p}

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

Den Startzustand darfst du selbst festlegen. Ich weiß nicht, was du mit "Anzahl der möglichen Wege und deren Länge" meinst. Ein DFA besteht aus Zuständen, Eingabealphabet, Übergansfunktion, Startzustand und akzeptierenden Zuständen. Wege und Längen kommen in der Definition eines DFA nicht vor.

Comments

Wie der DFA aussehen muss, wird er vermutlich wissen, da aber die Länge p nicht gegeben ist, kann er keinen DFA für die allgemeine Lösung aufstellen. Die Teillösung ist ein lösbares Rätsel.