Howto: Grammatik finden

1) Bild von https://commons.wikimedia.org/wiki/File:Swedish_license_plate_2019.jpg, die Datei ist lizenziert unter der Creative-Commons-Lizenz "Namensnennung – Weitergabe unter gleichen Bedingungen 4.0 international". Urheber ist der Wikipedia Nutzer "Andif1" Die Kfz-Kennzeichen in Schweden (schwedisch registreringsskyltar für die Schilder, registreringsnummer für die Nummer) basieren seit 1973 auf einem überregionalen System, bei dem das Fahrzeug eine Seriennummer zugewiesen bekommt, die auch bei Besitzerwechsel beim Fahrzeug verbleiben.

Die Seriennummer besteht aus zwei Blöcken. Der erste Block besteht immer aus drei Buchstaben, der zweite aus drei Ziffern oder zwei Ziffern gefolgt von einem Buchstaben.

Was sind die Terminalsymbole, aus denen das Alphabet Σ besteht?

In unserem Fall bestehen alle Worte der "Sprache" (die Kennzeichen) aus Zahlen und Buchstaben sowie einem Leerzeichen2) Der Unterstrich soll für ein Leerzeichen stehen , damit ist Σ={0,1,2,3,4,5,6,7,8,9,A,B,C,…,X,Y,Z,_}.

Strukturanalyse: Wie werden gültige Worte aus den Terminalsymbolen gebildet?

Hier wird oft bereits deutlich, welche weiteren Variablen man benötigt, um die Worte zu bilden: Bei diesem Beispiel sieht man unmittelbar ein, dass jedes Kennzeichen aus einem Buchstabenblock mit drei Buchstaben , gefolgt von einem Leerzeichen, gefolgt von einem weiteren Block, der entweder aus drei Ziffern besteht oder aus zwei Ziffern und einem Buchstabe.

In einem Syntaxdiagramm kann man das folgendermaßen darstellen (Unterstrich ist Leerzeichen):

Code für Bottlecaps

https://www.bottlecaps.de/rr/ui

Kennzeichen ::= BSBlock Leerzeichen ZBBlock
Leerzeichen ::= '_'
BSBlock ::= Buchstabe Buchstabe Buchstabe
ZBBlock ::= (Ziffer Ziffer Ziffer | Ziffer Ziffer Buchstabe)
Ziffer ::= ('0'|'1'|'2'|'...'|'8'|'9')
Buchstabe ::= ('A'|'B'|'C'|'...'|'X'|'Y'|'Z')

Productions P aus dem Syntaxdiagramm ableiten

Nun kann man die Regeln (Productions P) fast direkt ablesen:

S -> B1 _ B2
B1 -> BS BS BS
B2 -> Z Z Z | Z Z BS
BS -> A|B|C|...|X|Y|Z
Z -> 0|1|2|3|...|8|9

Grammatik aufschreiben

Jetzt kann man die Grammatik formal aufschreiben:

G=(V,Σ,P,S) mit V={S,B1,B2,BS,Z}, Σ={0,1,2,3,4,5,6,7,8,9,A,B,C,…,X,Y,Z,_} und

P = {
S → B1 _ B2
B1 → BS BS BS
B2 → Z Z Z | Z Z BS
BS → A|B|C|…|X|Y|Z
Z → 0|1|2|3|…|8|9
}

—-

(A1)

Die neue Verkehrsministerin legt fest, dass der zweite Block nicht mit einer Null beginnen darf. Passe die Grammatik entsprechend an.