Informatik 12/13 (G9)

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 nachfolgend Menge von Produktionsregeln $P$:

(1) <Kennzeichen> -> <Ort> " " <Mittelteil> " " <NummerE>
(2) <Ort> -> <Buchstabe> | <Buchstabe><Buchstabe> | <Buchstabe><Buchstabe><Buchstabe>
(3) <Mittelteil> -> <Buchstabe> | <Buchstabe><Buchstabe>
(4) <NummerE> = <Nummer> | <Nummer> "E"
(5) <Nummer> = <Ziffer> | <Ziffer><Ziffer> | <Ziffer><Ziffer><Ziffer>
(6) <Buchstabe> = "A" | "B" | ... | "Z" | "Ä" | "Ö" | "Ü"
(7) <Ziffer> = "0" | "1" | "2" | ... | "9"

b) $$<Kennzeichen>\xrightarrow[]{(1)}<Ort> "\ " <Mittelteil> "\ " <NummerE>\xrightarrow[]{(2)}<Buchstabe><Buchstabe><Buchstabe>"\ " <Mittelteil> "\ " <NummerE>\xrightarrow[]{dreimal\ (6)}$$ $$\mathrm{SOB"\ "}<Mittelteil> "\ " <NummerE>\xrightarrow[]{(5)}$$ $$\mathrm{SOB"\ "}<Mittelteil> "\ " <Nummer>"E"\xrightarrow[]{(4)}$$ $$\mathrm{SOB"\ "}<Mittelteil> "\ " <Ziffer><Ziffer>"E"\xrightarrow[]{(zweimal\ 7)}$$ $$\mathrm{SOB"\ "}<Mittelteil> "\ " 12E\xrightarrow[]{(3)}$$ $$\mathrm{SOB"\ "}<Buchstabe><Buchstabe> "\ " 12E\xrightarrow[]{zweimal\ (6)}$$ $$\mathrm{SOB\ AX\ 12E}$$