Aufgabe 3
a) Geben Sie eine Grammatik an, die Sprache beschreibt, in der deutsche Autokennzeichen notiert werden.
- Die Sprache soll alle Autokennzeichen der Formen "ND WW 16" und "IN XE 312E" beschreiben (Ortskürzel mit bis zu drei Buchstaben, Zwischenbereich mit bis zu zwei Buchstaben, ein- bis dreistellige Zahl, optional "E" am Ende).
- Auch nichtexistente Ortskürzel dürfen vorkommen.
b) Geben Sie zur Grammatik aus a) die Ableitung des Kennzeichens "SOB AX 12E" an.
Lösung
a)
Gegeben sei die formale Grammatik $G = (V, A, P, S)$ mit
- der Menge der Nichtterminale $V = \{<Kennzeichen>, <Ort>, <Mittelteil>, <NummerE>, <Buchstabe>, <Nummer>, <Ziffer>\}$
- dem Alphabet $A = \{A, B, C, \ldots, Z, Ä, Ö, Ü, 0, 1, 2, \ldots, 9\}$
- Startsymbol $S = <Kennzeichen>$
- der nachfolgenden Menge von Produktionsregeln $P$:
R1: Kennzeichen - Ort " " Mittelteil " " NummerE R2: Ort - Buchstabe | BuchstabeBuchstabe | BuchstabeBuchstabeBuchstabe R3: Mittelteil - Buchstabe | BuchstabeBuchstabe R4: NummerE = Nummer | Nummer "E" R5: Nummer = Ziffer | ZifferZiffer | ZifferZifferZiffer R6: Buchstabe = "A" | "B" | ... | "Z" | "Ä" | "Ö" | "Ü" R7: Ziffer = "0" | "1" | "2" | ... | "9"
b) $$Kennzeichen\xrightarrow[]{(R1)}Ort "\ " Mittelteil "\ " NummerE\xrightarrow[]{(R2)}Buchstabe\ Buchstabe\ Buchstabe"\ " Mittelteil "\ " NummerE\xrightarrow[]{dreimal\ (R6)}$$ $$\mathrm{"SOB\ "}Mittelteil "\ " NummerE\xrightarrow[]{(R5)}$$ $$\mathrm{"SOB\ "}Mittelteil "\ " Nummer"E"\xrightarrow[]{(R4)}$$ $$\mathrm{"SOB\ "}Mittelteil "\ " Ziffer\ Ziffer"E"\xrightarrow[]{(Rzweimal\ 7)}$$ $$\mathrm{"SOB\ "}Mittelteil "\ " "12E"\xrightarrow[]{(R3)}$$ $$\mathrm{"SOB\ "}Buchstabe\ Buchstabe "\ " "12E"\xrightarrow[]{zweimal\ (R6)}$$ $$\mathrm{"SOB\ AX\ 12E"}$$
Natürlich könnte man diese Lösung noch verbessern, z.B. indem man Vornullen bei der Zahl ausschließt.