|
|
 | | From: | Karl Pech | | Subject: | Grammatik_für_Nullen | | Date: | Sat, 23 Oct 2004 12:37:15 +0200 |
|
|
 | Hi,
Ich hab' im Moment keine Idee zu einer Aufgabe und hoffe, daß ihr mir
da helfen könnt.
Ich muß eine Grammatik G = (V, T, P, S) für die Sprache
L(G) = {0^n : n ist eine Quadratzahl} konstruieren mit V = {A, B, C, L, S} und
T = {0}.
Einige Regeln hat man uns vorgegeben(, wobei ich die letzten beiden Regeln selbst
hingeschrieben habe):
P = {
S -> LA
A -> BC|BAC
BC -> CB00
CB0 -> \epsilon
}
Nun steht das als letzter Tip man solle die Summenformel für n ungerade Zahlen
benutzen, denn diese Summe ist gleich n^2. Daraufhin habe ich versucht, die Summenformel
rekursiv zu definieren:
b_0 = 1
b_k = b_{k-1} + 2k + 1 ; k > 1
Die meisten Grammatiken sind offenbar rekursiv aufgebaut. Deshalb habe ich mir gedacht, daß
es dadurch einfacher wird die Lösung zu "sehen". Bisher fehlt mir allerdings dieser
"Geistesblitz". :(
Habt ihr eventuell einen weiteren Denkanstoss für mich?
Vielen Dank!
Viele Grüße
Karl
|
|
| | From: | Christoph Sorge | | Subject: | Re: Grammatik_für_Nullen | | Date: | Sun, 24 Oct 2004 02:28:50 +0200 |
|
|
| Karl Pech schrieb:
> Nun steht das als letzter Tip man solle die Summenformel für n ungerade Zahlen
> benutzen, denn diese Summe ist gleich n^2. Daraufhin habe ich versucht, die Summenformel
> rekursiv zu definieren:
>
> b_0 = 1
> b_k = b_{k-1} + 2k + 1 ; k > 1
>
Vielleicht hilft folgendes weiter:
Beginne mal, angefangen bei b_1, aufzuschreiben, wie viele Nullen Du für
jeden Teil der Gleichung brauchst und überlege dann, wie Du das mit der
Grammatik hinbekommen kannst.
Christoph
|
|
|
