endlichen Automaten bauen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo Leute,
(Ich hab' diese Frage auch ![[]](/images/popup.gif) hier gestellt.)
Ich habe Probleme mit folgender Aufgabe:
Entwerfen Sie eine Grammatik für die Sprache [m]L = \left\{0^n:\text{n ist eine Quadratzahl}\right\}[/m].
(Tip zu (b): Erzeugen Sie schrittweise eine Grammatik [m]G = \left(V, \Sigma, P, S\right)[/m] mit $V = [mm] \left\{A,B,C,L,S\right\}$ [/mm] und [m]\Sigma = \left\{0\right\}[/m]. Erzeugen Sie im ersten Schritt mit $S [mm] \rightarrow [/mm] LA$ und $A [mm] \rightarrow [/mm] BC|BAC$ Satzformen der Form [mm] $LB^nC^n$ [/mm] mit [m]n \ge 1[/m]. Im zweiten Schritt wird nun [mm] $LB^nC^n$ [/mm] zu [mm]0^{n^2}[/mm] abgeleitet.
Fügen Sie hierzu eine Regel hinzu, durch die das am weitesten links stehende C durch Vertauschungen mit B nach links bewegt werden kann und bei jeder Vertauschung zwei Nullen erzeugt. Am linken Ende angekommen benötigt man nun eine Regel, durch die das C gelöscht, sowie ein B und eine 0 entfernt werden kann. Es entsteht eine Satzform mit 2n-1 Nullen, n-1 B's und n-1 C's. Überlegen Sie sich nun, wie man durch weitere Vertauschungsregeln und Löschregeln unter Verwendung der Tatsache, daß [mm] $\sum_{k=1}^{n} [/mm] (2k-1) = [mm] n^2$ [/mm] ist,
ans Ziel kommt.
Nun hat man mir im Mathe-Forum bereits gesagt, daß sich diese Summe auch rekursiv angeben läßt. Ich hatte das gefragt, weil solche Grammatiken
ja normalerweise rekursiv aufgebaut sind. Aber hier hat mir das leider nichts genützt. :(
Also hier die rekursive Form:
[mm] $b_0 [/mm] = 1$
[mm] $b_k [/mm] = [mm] b_{k-1} [/mm] + 2k + 1 ; k > 1$
Was jemand einen Rat?
Danke!
Viele Grüße
Karl
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:24 Sa 06.11.2004 | | Autor: | Karl_Pech |
Hi Leute!
Wir hatten schon seit einiger Zeit die Lösung dazu besprochen:
[Dateianhang nicht öffentlich]
Grüße
Karl
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:08 Di 16.11.2004 | | Autor: | PhiBa |
Hallo,
folgende gültige Ableitung führt nicht zu einem Wort der Sprache:
S -> LA -> LBAC -> LBBACC -> LBB00CC -> LBB00C0 -> LBB0000 -> LB00000 ->
L000000 -> 000000
Man muss die Projektionen ja nicht in der Reihenfolge verwenden. Also erzeugt die Grammatik nicht die angegebene Sprache.
Ich würde mal folgende Grammatik vorschlagen:
V = {A,B,C,L,R,S}
P = {
S -> 0
S- > LCABR
A -> CB|CAB
BC -> C0B
B0 -> 0B
0C -> C0
LC -> L
BR -> R
L0 -> 0
0R -> 0
}
Müsste eigentlich gehen.
MfG Philipp
|
|
|
|
