Alphabet: < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:07 Sa 14.04.2012 | | Autor: | bandchef |
| Aufgabe | Seien [mm] $\Sigma$ [/mm] ein Alphabet $a [mm] \in \Simga$ [/mm] und $w [mm] \in \Sigma^{\star}$.
[/mm]
Geben sie eine induktive Definition an für die Operation [mm] $|w|_a$ [/mm] an, die zählt, wie oft der Buchstabe a in dem Wort w vorkommt.
Demonstrieren sie die Anwendung der Definition am Beispiel [mm] $|aba|_a$ [/mm] |
Hi Leute!
Meine Lösung:
1.) [mm] $|\epsilon| [/mm] = 0$
2.) Falls $w = [mm] K_s(v,a)$, [/mm] so [mm] $|w|_a [/mm] = [mm] |v|_a+1$ [/mm] für $w,v [mm] \in \Sigma^{\star}$ [/mm] und $a [mm] \in \Sigma$
[/mm]
Bei der Demonstration meiner Definition hab ich nun Probleme...
Ich hab hier im Skript eine Beispiel angegeben:
Betrachte [mm] $w=010\in \Sigma^{\star}_{Bool}. [/mm] Für $|010|$ erhalten wir:
$|010| = |01| + 1$, denn [mm] $K_s(01,0) [/mm] = 010$
$|01| = |0| + 1$, denn [mm] $K_s(0,1) [/mm] = 01$
$|0| = [mm] |\epsilon| [/mm] + 1$, denn [mm] $K_s(\epsilon,0) [/mm] = 0$
[mm] $|\epsilon| [/mm] = 0$ per Definition
Es ergibt sich also:
$|010| = |01| + 1 = |0| + 1 + 1 = [mm] |\epsilon| [/mm] + 1 + 1 + 1 = 0 + 1 + 1 + 1 = 3$
Offenbar ist [mm] $|010|_1 [/mm] = 1$ und [mm] $|010|_0 [/mm] = 2$.
Wenn ich nun dieses Beispiel auf die Aufgabe oben anwende, weiß ich nicht recht ob das stimmt:
$|aba| = |ab| + 1$, denn [mm] $K_s(ab,a) [/mm] = aba$
$|ab| = |a| + 1$, denn [mm] $K_s(a,b) [/mm] = ab$
$|a| = [mm] |\epsilon| [/mm] + 1$, denn [mm] $K_s(\epsilon,a) [/mm] = a$
[mm] $|\epsilon| [/mm] = 0$ per Definition
Es ergibt sich also:
$|aba| = |ab| + 1 = |a| + 1 + 1 = [mm] |\epsilon| [/mm] + 1 + 1 + 1 = 0 + 1 + 1 + 1 = 3$
Offenbar ist [mm] $|aba|_a [/mm] = 2$
Kann man das dann so schreiben? Ist das richtig?
|
|
| |
|
Hallo,
> Seien [mm]\Sigma[/mm] ein Alphabet [mm]a \in \Simga[/mm] und [mm]w \in \Sigma^{\star}[/mm].
>
> Geben sie eine induktive Definition an für die Operation
> [mm]|w|_a[/mm] an, die zählt, wie oft der Buchstabe a in dem Wort w
> vorkommt.
>
> Demonstrieren sie die Anwendung der Definition am Beispiel
> [mm]|aba|_a[/mm]
> Hi Leute!
>
> Meine Lösung:
>
> 1.) [mm]|\epsilon| = 0[/mm]
> 2.) Falls [mm]w = K_s(v,a)[/mm], so [mm]|w|_a = |v|_a+1[/mm]
> für [mm]w,v \in \Sigma^{\star}[/mm] und [mm]a \in \Sigma[/mm]
in 2. musst du noch [mm]|w|_a[/mm] für den Fall [mm]w=K_s(v,x),\ x\neq a[/mm] definieren. Dann wird auch die Demonstration keine Probleme mehr machen. Ich würde es sogar noch etwas anders aufziehen:
1.) [mm]|\epsilon| = 0[/mm], [mm]|x|_a=[/mm]? für [mm]x\in\Sigma[/mm]
2.) [mm]|wx|_a=|w|_a+|x|_a[/mm] für [mm]w\in\Sigma^{\*},\ x\in\Sigma.[/mm]
>
> Bei der Demonstration meiner Definition hab ich nun
> Probleme...
>
>
>
>
>
> Ich hab hier im Skript eine Beispiel angegeben:
>
> Betrachte [mm]$w=010\in \Sigma^{\star}_{Bool}.[/mm] Für $|010|$
> erhalten wir:
>
> [mm]|010| = |01| + 1[/mm], denn [mm]K_s(01,0) = 010[/mm]
> [mm]|01| = |0| + 1[/mm],
> denn [mm]K_s(0,1) = 01[/mm]
> [mm]|0| = |\epsilon| + 1[/mm], denn
> [mm]K_s(\epsilon,0) = 0[/mm]
> [mm]|\epsilon| = 0[/mm] per Definition
>
> Es ergibt sich also:
>
> [mm]|010| = |01| + 1 = |0| + 1 + 1 = |\epsilon| + 1 + 1 + 1 = 0 + 1 + 1 + 1 = 3[/mm]
>
> Offenbar ist [mm]|010|_1 = 1[/mm] und [mm]|010|_0 = 2[/mm].
>
>
>
>
>
> Wenn ich nun dieses Beispiel auf die Aufgabe oben anwende,
> weiß ich nicht recht ob das stimmt:
>
> [mm]|aba| = |ab| + 1[/mm], denn [mm]K_s(ab,a) = aba[/mm]
> [mm]|ab| = |a| + 1[/mm],
> denn [mm]K_s(a,b) = ab[/mm]
> [mm]|a| = |\epsilon| + 1[/mm], denn
> [mm]K_s(\epsilon,a) = a[/mm]
> [mm]|\epsilon| = 0[/mm] per Definition
>
>
> Es ergibt sich also:
>
> [mm]|aba| = |ab| + 1 = |a| + 1 + 1 = |\epsilon| + 1 + 1 + 1 = 0 + 1 + 1 + 1 = 3[/mm]
>
> Offenbar ist [mm]|aba|_a = 2[/mm]
>
>
> Kann man das dann so schreiben? Ist das richtig?
Nein.
Gruß
Spunk
|
|
|
|
