Grammatik für eine Sprache < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Finden sie eine Grammatik, welche die sprache [mm] L_4 [/mm] = [mm] {a^(n^2-1) | n \ge 1} [/mm] erzeugt. |
Hallo,
ich komme bei dieser Grammatik nicht weiter, da das wachstum quadratisch ist und ich nur lineares Wachstum kenne und auch nichts über quadratisches Wachstum in meinen Büchern gefunden habe.
Die Reihenfolge der Wörter wäre quasi so:
[mm] \epsilon [/mm] (eigentlich ja 1 aber ich gehe davon aus sie meinen dass das leere Wort damit gemeint ist, da die Sprache über {a} ist)
aaa (3)
aaaa aaaa (8)
aaaaa aaaaa aaaaa (15)
aaaaa aaaaa aaaaa aaaaaa aaaa (24)
.
.
.
Hat jemand da einen Tipp, wie man so etwas darstellen könnte?
Gruß Phil
|
|
| |
|
moin Phil,
Soll die Grammatik endlich sein?
Wenn nein könnte ich spontan diese empfehlen:
$L = [mm] A_i$ [/mm] für $i [mm] \in \IN$
[/mm]
[mm] $A_i [/mm] = [mm] (B_{i+1})^{i-1}$ [/mm] (wobei [mm] $(A_i)^0$ [/mm] das leere Wort sei)
[mm] $B_i [/mm] = [mm] a^i$
[/mm]
Dies benutzt einfach nur die Tatsache, dass [mm] $n^2-1 [/mm] = (n-1)(n+1)$.
Sollte die Grammatik endlich sein oder sonst eine "schönere" Form haben, fällt mir spontan leider auch nix ein.
lg
Schadow
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Sa 14.04.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
