===== 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$:
<code>
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"
</code>
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"}$$

<WRAP center round tip 60%>
Natürlich könnte man diese Lösung noch verbessern, z.B. indem man Vornullen bei der Zahl ausschließt.
</WRAP>