Grammatik für Nummernschilder

[SharkFoce]

Guten Tag,

wir haben in der Schule mit dem Thema der formalen Sprache angefangen und auf dem ersten Blick überfordert mich dieses Thema sehr und youtube tutorials bringen mich leider auch nicht weiter. Aufgegeben wurde uns eine reguläre Grammatik zur Erstellung von "deutschen" Nummernschildern (XXX - XX - 1234). Könnte mir jemand eine kleine Einleitung zum Thema geben und eventuell ein Ansatz?


Gruß

 

[neoexpert]

Ich versuch's:
Kleinbuchstaben sind im folgenden Variablen, s ist startsymbol, "|" steht für entweder oder:
a->A|B|C|...|Z
b->0|1|2|3|...|9
s->ac
c->ad
d->ae
e->-f
f->ag
g->ah
h->-j
j->bk
k->bl
l->bm
m->b

 

[SharkFoce]

Also könnt ich wenn a -> A-Z ist und b -> 0-9 ist, eigentlich die Aufgabe lösen oder?
S-> a -> a -> a -> a -> a -> b -> b -> b -> b / XXX-XX-0123 ?

 

[neoexpert]

Jo, aber manchmal gibt es Nummerschilder mit nur 2 oder einem Buchstaben für die Region. Für Historische Autos kann man hinter der Zahl ein "H" anhängen. Und die Zahl-Länge kann sich variieren.

 

[SharkFoce]

Ok und wie würde man jetzt formal die Grammatik aufschreiben (irgendwas mit 4 Tupeln?) Und wie könnt ich Kennzeichen X-XX-01 im oben erwähnten zeigen?

 

[neoexpert]

Sagen wir mal entweder ein oder Zwei Buchstaben würde man so machen:
a->A|B|C|...|Z
s->a
s->ab
b->a
man kann also die gewünschte Regel für s auswählen.

 

[Meniskusschaden]

Ich versuch's:
Kleinbuchstaben sind im folgenden Variablen, s ist startsymbol, "|" steht für entweder oder:
a->A|B|C|...|Z
b->0|1|2|3|...|9
s->ac
c->ad
d->ae
e->-f
f->ag
g->ah
h->-j
j->bk
k->bl
l->bm
m->b

Kann man das wirklich so machen? Kenne mich da nicht wirklich aus, aber es kommt mir etwas seltsam vor. Beispiel:

s     Startsymbol
ac    Startsymbol ersetzt
Ac    a durch Terminal A ersetzt
Aad   c durch ad ersetzt
ABd   a durch Terminal B ersetzt
ABae  d durch ae ersetzt
ABCe  a durch Terminal C ersetzt
ABC-f e durch -f ersetzt
usw.

Wie bildet man dann beispielsweise einen einzelnen Buchstaben für den Ort ab?

 

[neoexpert]

Achso:
G=(N,T,P,S)
N= Nichtterminale (Variablen)
T= Terminale (Konstanten)
P = Menge aller Regeln (die oben)
S= startsymbol

 

[SharkFoce]

Also wär es formal damit eine Maschine die Sprache versteht, es doch so oder? - die Grammatik also
G = (N,T,S,P)
N = (S,A,B)
T = (a,b) a = A|B|C|...|Z b = 0-9
Startsymbol S:
P = was wären die Produktionsvorschriften?

 

[neoexpert]

Maschine nicht. Mit Grammatiken kann man Sprachen erzeugen. Automaten akzeptieren Sprachen.
In P schreibst du Mengenmässig alle deine Regeln auf. Z.B:
P={S->aB,B->a}

 

[neoexpert]

Kann man das wirklich so machen? Kenne mich da nicht wirklich aus, aber es kommt mir etwas seltsam vor. Beispiel:

s     Startsymbol
ac    Startsymbol ersetzt
Ac    a durch Terminal A ersetzt
Aad   c durch ad ersetzt
ABd   a durch Terminal B ersetzt
ABae  d durch ae ersetzt
ABCe  a durch Terminal C ersetzt
ABC-f e durch -f ersetzt
usw.

Wie bildet man dann beispielsweise einen einzelnen Buchstaben für den Ort ab?

Ja das muss man auch beachten, hab oben schon geschrieben. Ich wollte nur seinen Beispiel umsetzen. (XXX-XX-1234)

 

[SharkFoce]

Alles klar, war aber T richtig?

Danke

 

[neoexpert]

Ne. In T kommen alle Konstanten:
T={1,2,3,...,9,A,B,C,...,Z}

 

[SharkFoce]

Oh und muss ich nicht irgendwo a und b definieren?

 

[Meniskusschaden]

Ja das muss man auch beachten, hab oben schon geschrieben. Ich wollte nur seinen Beispiel umsetzen. (XXX-XX-1234)

Ach so. Ich dachte erst, dass es bereits das vollständige Regelwerk sein soll.

 

[neoexpert]

Das sind die Variablen (aber Vorsicht ich habe oben das so festgelegt, weil wir Großbuchstaben brauchen. Normalerweise verwendet man Großbuchstaben für Variablen und Kleinbuchstaben für Konstanten)
Variablen kommen alle in N={a,b,c,...}

 

[SharkFoce]

Also könnt ich jetzt meine Aufgabe "Entwickeln Sie eine reguläre Grammatik zur Erstellung von Nummernschildern" mit dieser folgenden Grammatik beantworten;
G = (N,T,S,P)
N =(S,A,B)
T = (1,2,3,...,9,a,b,c,...,z)
Startsymbol S:
P = S->ac
c->ad
d->ae
e->-f
f->ag
g->ah
h->-j
j->bk
k->bl
l->bm
m->b

Danke schon mal im voraus

 

[neoexpert]

Eig nicht. Versuch damit mal
M-CM-9000 zu erzeugen.
Wir wollen ja nicht einfach nur Lösungen liefern, viel mehr Denkanstöße.
EDIT:
Und ausserdem ist P bei dir keine Menge.

 

[SharkFoce]

P = S->mA -> cA -> mA -> 9B -> 0B -> 0B -> 0B <-- aber B darf ja nicht zum Schluss allein stehen oder?

 

[neoexpert]

Das letztere ist was seltsam.
Erzeugen von Wörtern geht so wie @Meniskusschaden (Hoffentlich kann er noch laufen) gemacht hat.

 

[neoexpert]

s ->
ac ->
Ac ->
Aad ->
ABd ->
ABae ->
ABCe ->
ABC-f -> ...
usw.