formale Sprachen, eine Grammatik aufstellen?
Grammatik für Uhrzeit (HH:MM:SS) aufstellen und welcher Typ
Ich weiß die Stunden können von 00 bis 24 gehen, die Minuten von 00 bis 59 und die Sekunden von 00 bis 59
S -> A
A -> ...
Wie krieg ich das als Grammatik einer formalen Sprache hin?
1 Antwort
Um eine Grammatik für die Uhrzeit im Format HH:MM:SS aufzustellen, die Stunden von 00 bis 23, die Minuten von 00 bis 59 und die Sekunden ebenfalls von 00 bis 59 berücksichtigt, müssen wir zuerst definieren, wie Zahlen in diesem Bereich erzeugt werden können. Die Grammatik, die wir aufstellen, wird eine kontextfreie Grammatik sein, also Typ-2 nach der Chomsky-Hierarchie.
Schritt 1: Definieren der Nonterminals und Terminals
- **Nonterminals**: S (Start), A (Stunden), B (Minuten und Sekunden)
- **Terminals**: Ziffern (0-9) und der Doppelpunkt (:)
Schritt 2: Aufstellen der Produktionen
S -> A:B:B (Stunden, Minuten und Sekunden getrennt durch Doppelpunkte)
A -> 0H | 1H | 20 | 21 | 22 | 23 (Stunden von 00 bis 23)
B -> 0M | 1M | 2M | 3M | 4M | 5M (Minuten und Sekunden von 00 bis 59)
H -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (Erlaubt Zahlen von 00 bis 09 sowie 10 bis 19)
M -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (Erlaubt Zahlen von 00 bis 09 sowie 10 bis 59)
Zusammenfassung der Grammatik
Die Grammatik sieht dann so aus:
S -> A:B:B
A -> 0H | 1H | 20 | 21 | 22 | 23
B -> 0M | 1M | 2M | 3M | 4M | 5M
H -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
M -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Diese Grammatik ist eine kontextfreie Grammatik (Typ-2 nach Chomsky), da alle Regeln die Form \(N \to \alpha\) haben, wobei \(N\) ein Nichtterminalsymbol ist und \(\alpha\) eine beliebige Kette von Terminal- und/oder Nichtterminalsymbolen ist. Jede Produktionsregel transformiert ein Nichtterminal in eine Kombination von Terminalen und/oder anderen Nichtterminalen, ohne Kontext oder zusätzliche Bedingungen für die Anwendung dieser Regeln zu berücksichtigen.
Beste Grüße,
ChatGPT
Die erste Zeile sollte eigentlich auch korrekt sein. Minuten und Sekunden sind ja beide 00 bis 59, also wie in B definiert. Mein Informatik-Studium ist schon etwas her, aber ich glaube, das passt.
Dabei ist noch wichtig zu erwähnen, dass die angegebene Grammatik zwar Typ-2 sein mag, die Sprache allerdings eine reguläre, also Typ-3 Sprache ist (Beweis trivial, da die Sprache endlich ist).
Bis auf die erste Zeile mit
S -> A:B:B
schaut des eigentl. gut aus.
Kann man des so machen?