Howto: Grammatik finden

¹⁾ 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.

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

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 (BSBlock) mit drei Buchstaben , gefolgt von einem Leerzeichen (Terminalsymbol), gefolgt von einem weiteren Block (ZBBlock), der entweder aus drei Ziffern besteht oder aus zwei Ziffern und einem Buchstabe.

Dann überlegt man sich, wie die Blöcke gebildet werden - möglicherweise benötigt man dazu weitere "Unterblöcke mit entsprechenden Variablen - und so weiter, bis man bei den Terminalsymbolen anlangt.

In einem Syntaxdiagramm kann man das für unser Beispiel folgendermaßen darstellen (Unterstrich ist Leerzeichen):

Code für Bottlecaps

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')

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 

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
}

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

Lösungshinweis (Bottlecap)

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