Anzahl versch. Akzeptoren < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Gegeben ist eine Zustandsmenge Z = {z0,z1,z2,z3} und ein Eingabealphabet X = {a,b,c}.
Geben Sie einen arithmetischen Ausdruck für die Anzahl verschiedener endlicher Akzeptoren mit der genannten Zustandsmenge und dem genannten Eingabealphabet an. |
Ich weiß schonmal, die Lösung ist 4^12 * [mm] 2^4 [/mm] * 4 = 2^30, wie sie sich genau zusammensetzt ist mir allerdings noch nicht klar.
Herausbekommen habe ich folgendes:
Die 4 steht für die verschiedenen Möglichkeiten, den Startknoten zu wählen und die [mm] 2^4 [/mm] sind die Anzahl der verschiedenen Möglichkeiten, die zu akzeptierenden Knoten zu wählen. (4 Möglichkeiten, genau einen zu wählen, 6 Möglichkeiten 2 zu akzeptieren, 4 Möglichkeiten 3 zu akzeptieren und jeweils 1 Möglichkeit, entweder alle oder keinen zu akzeptieren)
Bei der 4^12 haperts jetzt noch. Mir ist klar, dass das mit der Anordnung der Knoten zu tun hat und welcher auf welchen Knoten folgt, aber warum genau 4^12?
Gruß und Danke
GHoernle
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:31 Mi 01.09.2010 | | Autor: | felixf |
Moin!
> Gegeben ist eine Zustandsmenge Z = {z0,z1,z2,z3} und ein
> Eingabealphabet X = {a,b,c}.
>
> Geben Sie einen arithmetischen Ausdruck für die Anzahl
> verschiedener endlicher Akzeptoren mit der genannten
> Zustandsmenge und dem genannten Eingabealphabet an.
> Ich weiß schonmal, die Lösung ist 4^12 * [mm]2^4[/mm] * 4 = 2^30,
> wie sie sich genau zusammensetzt ist mir allerdings noch
> nicht klar.
>
> Herausbekommen habe ich folgendes:
>
> Die 4 steht für die verschiedenen Möglichkeiten, den
> Startknoten zu wählen
![[ok]](/images/smileys/ok.gif "[ok]")
> und die [mm]2^4[/mm] sind die Anzahl der
> verschiedenen Möglichkeiten, die zu akzeptierenden Knoten
> zu wählen. (4 Möglichkeiten, genau einen zu wählen, 6
> Möglichkeiten 2 zu akzeptieren, 4 Möglichkeiten 3 zu
> akzeptieren und jeweils 1 Möglichkeit, entweder alle oder
> keinen zu akzeptieren)
Genau. Du hast viermal die Moeglichkeit, "ja" oder "nein" auszuwaehlen.
> Bei der 4^12 haperts jetzt noch. Mir ist klar, dass das mit
> der Anordnung der Knoten zu tun hat und welcher auf welchen
> Knoten folgt, aber warum genau 4^12?
Nun, du hast vier Knoten, und fuer jeden Knoten hast du drei Folgezustaende -- je nach Eingabebuchstaben. Du kannst also $4 [mm] \cdot [/mm] 3$ mal einen Nachfolgeknoten waehlen, und dafuer hast du 4 Moeglichkeiten. Also gibt es insgesamt [mm] $4^{4 \cdot 3}$ [/mm] Wahlmoeglichkeiten.
LG Felix
|
|
|
| |
|
>
> Nun, du hast vier Knoten, und fuer jeden Knoten hast du
> drei Folgezustaende -- je nach Eingabebuchstaben. Du kannst
> also [mm]4 \cdot 3[/mm] mal einen Nachfolgeknoten waehlen, und
> dafuer hast du 4 Moeglichkeiten. Also gibt es insgesamt
> [mm]4^{4 \cdot 3}[/mm] Wahlmoeglichkeiten.
>
> LG Felix
>
Ich habe es fast verstanden, komme jetzt aber nicht dahinter warum 4^12 und nicht [mm] 12^4.
[/mm]
Habe ich beispielsweise ein Byte, welches aus 8 Bit besteht, so ist es einfach, ich habe [mm] 2^8 [/mm] Möglichkeiten, da ich 8 Mal zwischen 0 und 1 wählen kann.
Hier bereitet mir jetzt noch Probleme, dass es insgesamt 3 Stationen gibt: Startknoten, Übergang und Zielknoten.
Betrachte ich es aus der Weise wie du beschrieben hast, also Startknoten und Übergang, dann die Zielknoten, so komme ich auch auf 4^12. Wenn ich jetzt allerdings so herangehe, dass ich mir zunächst überlege, dass jeder der 4 Knoten 12 verschiedene Ausgänge haben kann, so hätte ich gemäß der Herangehensweise mit den 8 Bit auf [mm] 12^4 [/mm] getippt.
lg
ghoernle
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:27 Do 02.09.2010 | | Autor: | felixf |
Moin!
> > Nun, du hast vier Knoten, und fuer jeden Knoten hast du
> > drei Folgezustaende -- je nach Eingabebuchstaben. Du kannst
> > also [mm]4 \cdot 3[/mm] mal einen Nachfolgeknoten waehlen, und
> > dafuer hast du 4 Moeglichkeiten. Also gibt es insgesamt
> > [mm]4^{4 \cdot 3}[/mm] Wahlmoeglichkeiten.
>
> Ich habe es fast verstanden, komme jetzt aber nicht
> dahinter warum 4^12 und nicht [mm]12^4.[/mm]
>
> Habe ich beispielsweise ein Byte, welches aus 8 Bit
> besteht, so ist es einfach, ich habe [mm]2^8[/mm] Möglichkeiten, da
> ich 8 Mal zwischen 0 und 1 wählen kann.
Genau.
> Hier bereitet mir jetzt noch Probleme, dass es insgesamt 3
> Stationen gibt: Startknoten, Übergang und Zielknoten.
>
> Betrachte ich es aus der Weise wie du beschrieben hast,
> also Startknoten und Übergang, dann die Zielknoten, so
> komme ich auch auf 4^12.
Gut :)
> Wenn ich jetzt allerdings so
> herangehe, dass ich mir zunächst überlege, dass jeder der
> 4 Knoten 12 verschiedene Ausgänge haben kann, so hätte
> ich gemäß der Herangehensweise mit den 8 Bit auf [mm]12^4[/mm]
> getippt.
Nun, die Annahme, dass jeder der vier Knoten genau 12 verschiedene Ausgaenge hat, ist falsch. Deswegen stimmt auch [mm] $12^4$ [/mm] nicht. Die Anzahl der Ausgaenge ist [mm] $4^3$, [/mm] nicht $4 [mm] \cdot [/mm] 3$.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:33 Do 02.09.2010 | | Autor: | G-Hoernle |
[mm] (4^3)^4 [/mm] ... jetzt komme ich mit :) merci
|
|
|
|
