Reguläre Grammatik angeben für L aller Wörter über Epsilon (0,1); maximal viermal 1 in jedem Wort

Question

Frage:Reguläre Grammatik angeben für L aller Wörter über Epsilon (0,1); maximal viermal 1 in jedem Wort

Ich stehe gerade irgendwie auf dem Schlauch, wie ich auf 4 Einsen begrenze.

Ansatz:

S nach 0S | epsilon

S nach 1B |epsilon

B nach 1C | epsilon

C nach 1D | epsilon

D nach epsilon

Comments

Ich habe vergessen, dass man noch in der Lage sein muss, beliebig viele Nullen zu erzeugen:

S= Anfangszustand

S nach 0S | epsilon

S nach 1B |epsilon | 0B

B nach 1C | epsilon | 0C

C nach 1D | epsilon | 0D

D nach 1E | epsilon | 0E

E nach epsilon

Damit wären z.B. 1111 und 100100100100 in der Grammatik

Habe ich eventuell etwas übersehen?

Answer 1

Deine Antwort im Kommentar ist nicht ganz richtig, man sollte beim Schreiben von Nullen in der selben Regel bleiben, sonst kannst du ja auch nur maximal eine 0 zwischen zwei 1en machen. Dein Beispielwort lässt sich also nicht mit deiner Grammatik generieren, da du zwischen der dritten und vierten 1 nur eine einzige 0 machen kannst. Das Ganze sollte so aussehen:

$$S\to \epsilon \mid 0S \mid 1A\\A\to \epsilon \mid 0A \mid 1B\\B\to \epsilon \mid 0B \mid 1C \\C\to \epsilon \mid 0C \mid 1D \\D\to \epsilon \mid 0D$$

Außerdem brauchst zum Beispiel die Regel \(E\to \epsilon \) nicht, das kannst du ja schon in D mit der Regel machen.

Jetzt kannst du Wörter der Form \(\mathtt{\epsilon\cup \dots \cup (0^*.1.0^*.1.0^*.1.0^*.1.0^*)}\) erstellen. Man benutzt bei regulären Ausdrücken für \(\cup\) auch gerne \(+\) oder \(\mid\).

Comments

Vielen Dank für die Antwort.

Jetzt sehe ich es auch. Das hat mir sehr geholfen.

Wenn ich dazu einen DFA zeichne, habe ich ja 5 Zustände, wobei q0 der Anfangszustand und Q5 der Endzustand sind. Die Übergangsgraphen von q0 nach q1-4 wären mit Einsen zu versehen und bei den Zuständen q0-4 jeweils eine Schleife mit 0.

Muss ich im DFA das leere Wort irgendwie ausdrücken und können die Übergangsgraphen der Zustände q0-4 zum Endzustand (q5) unbeschriftet bleiben?

Müsste ich das leere Wort auch in die 0-Schleifen schreiben?

---

Ich sehe gerade oben, bei Eingabealphabet. Anstatt Sigma Epsilon geschrieben...oh man, wie peinlich.

Zum Glück hat man es trotzdem verstanden.

---

Epsilon im DEA bzw DFA hat sich auch erledigt, ist ja eine blöde Frage. Er braucht natürlich eine eindeutige Eingabe, ergibt sich schon aus der Definition.

Mein Problem ist nun, dass ich nicht weiß, wie ich im DFA von einer Eingabe eines Worts z.B. 00 in den Endzustand q5 komme.

---

Ja, genau. Du bleibst immer im selben Zustand beim Lesen von 0en und bei den 1en wechselst du zum nächsten Zustand.

Du musst einfach nur die Endzustände richtig festlegen. Für diese Grammatik wäre der Startzustand ein Endzustand, da ja das leere Worte auch erkannt wird. Außerdem ja auch alle anderen Zustände sind akzeptierende Zustände. In jedem Zustand haben wir ja die richtige Struktur von beliebig vielen 0en und nur maximal vier 1en.

---

Vielen Dank für die tollen Tips.

Ich hatte mir das kurz nachdem gedacht, als ich die Frage gestellt habe:)

---

@Chess Thematisch irrelevant, aber ich glaube wir sind in der gleichen Vorlesung :'D (LudS)?

---

@Chess Gern geschehen!