Wie setzte ich "höchstens" in einem DEA um?
Hallo, das ist eine Frage für die Informatiker unter euch: wie setzte ich die Bedienung "Höchstens" in einem deterministischen endlichen Automaten um?
Beispiel: wir haben die Sprache L1= {w | w hat höchstens eine 0 und mindestens zwei 1er} wie sieht der passende DEA dazu aus?
2 Antworten
Kleiner Hinweis zum Start: Ist schon etwas länger her, daher kann es durchaus sein, dass das nicht ganz korrekt ist.
Du kannst dir das ganze als "Fluss" vorstellen. Nach unten liest du immer eine 1, nach rechts z.B. eine 0
Du darfst beliebig oft nach unten, aber nur einmal die 0 nutzen.
Jetzt musst du drei Fälle unterscheiden:
- 0 direkt am Anfang
- 0 nach der ersten 1 (um sicherzustellen, dass da mindestens eine weitere 1 folgt)
- 0 nach mindestens zwei Einsen
Könnte z.B. so aussehen:
Da hast du Recht, ich hab das höchstens etwas übergangen und nur den Case "genau eine" behandelt
Bastel dir sechs Zustände für alle möglichen Anzahlen ({0, 1}×{0, 1, viele}). Die Übergänge sollten ja klar sein, wenn man zählen kann.
(0, 0) ist Start, und die Endzustände sind (0, viele) und (1, viele).
müsste q3 nicht auch ein Endzustand sein? Weil höchstens eine 0 bedeutet ja das auch keine vorkommen kann