Automaten konstruieren ε-NFA über Alphabet

Question

Frage:

Nach dem Standard ISO 8601 wird ein Datum in der Form JJJJ-MM-TT notiert. Beispielsweise
wird der 23. Juni 1912, durch 1912-06-23 repräsentiert.
Konstruieren Sie einen ε-NFA über dem Alphabet Σ = {0, 1, . . . , 9, -} mit möglichst wenigen
Zuständen, der genau die Zeichenketten aus Σ* akzeptiert, die ein Datum aus dem Jahr 2024
repräsentieren.

Leider habe ich keinerlei Ansätze, wie ich hier vorgehen kann. Wie würde eine Lösung aussehen?

Vielen Dank im Voraus.

Answer 1

\(q_{0}\stackrel{2}{\longrightarrow}q_{2}\stackrel{0}{\longrightarrow}q_{3}\stackrel{2}{\longrightarrow}q_{4}\stackrel{4}{\longrightarrow}q_{5}\stackrel{-}{\longrightarrow}q_{6}\begin{array}{l} \stackrel{0}{\nearrow}q_{7}\begin{cases} \stackrel{2}{\longrightarrow}q_{9} & \text{ 29 Tage}\\ \stackrel{4,6,9}{\longrightarrow}q_{10} & \text{ 30 Tage}\\ \stackrel{1,3,5,7,8}{\longrightarrow}q_{11} & \text{ 31 Tage} \end{cases}\\ \stackrel{1}{\searrow}q_{8}\begin{cases} \stackrel{0,2}{\longrightarrow}q_{11} & \text{ 31 Tage}\\ \stackrel{1}{\longrightarrow}q_{10} & \text{ 30 Tage} \end{cases} \end{array}\)

Comments

Super Danke, habe es nun verstanden :)

Answer 2

Ein paar Ideen:

1.) 2024 ist gefixt, d.h. der Automat muss zwingend ( ) -- 2 -- ( ) -- 0 -- ( ) -- 2 -- ( ) -- 4 ( ) -- .... verarbeiten können.

2.) Nach dem Jahr folgt der Monat bei JJJJ-MM-TT, hier sollte man dann eine oder mehrere Sinnvolle Bedingungen finden, denn Monate gibt es bekanntlich nur 12.

3.) Dann auf die Monate und deren Tage achten...