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.

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"}$$