Automat erstellen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 19:22 Sa 08.11.2008 | | Autor: | Guiniviere |
| Aufgabe | | Eine ISBN-Nummer ist eine zehnstellige Ziffernfolge a= a1....a10. Dabei gilt für die Ziffern: ai Element von {0,1,2,3,4,5,6,7,8,9}, 1<= i <=9, sowie a10 Element von {0,1,2,3,4,5,6,7,8,9,X}, wobei X für den Wert 10 steht. Eine ISBN-Nummer ist korrekt, genau dann, wenn [mm] \summe_{i=1}^{10} [/mm] i*a= 0mod11 gilt. Überprüfen Sie die Gültigkeit dieser Gleichung! Konstruieren Sie einen endlichen Automaten, der genau die korrekten ISBN-Nummern akzeptiert! |
Hallo liebe Alle 
Ich zerbreche mir nun seit zwei Wochen den Kopf über den zu konstruierenden Automaten und finde keinen Ansatz. Ich habe mir gedacht, dass man den Automaten etwa so schreiben könnte:
->start --> s1 --> s2 --> s3 --> s4 --> s5 --> s6 --> s7 --> s8 --> s9 --> s10 --> s11
dabei sind die Übergänge von s1 bis s9 durch die Ziffern (0,1,2,3,4,5,6,7,8,9) herbeiführbar
der Übergang von s9 zu s10 durch (0,1,2,3,4,5,6,7,8,9,X)
und der Übergang von s10 zu s11 durch die 0, wenn die Berechnung des Modulo11=0 ergeben hat.
Mein Problem dabei ist: Der Automat kann sich ja eigentlich "nichts merken". Also weiß er ja am Ende auch nicht, welche Ziffern vor dem erreichten Zustand eingegeben wurden. Somit ist eine Berechnung auch nicht möglich.
Hat jemand irgendeinen Ideenansatz, in welche Richtung ich bei der Konstruktion des Automaten denken muß? Ich bin da völlig planlos.
Vielen lieben Dank im Voraus dafür.
Guini
|
|
| |
|
Hallo Guiniviere!
> Eine ISBN-Nummer ist eine zehnstellige Ziffernfolge a=
> a1....a10. Dabei gilt für die Ziffern: ai Element von
> {0,1,2,3,4,5,6,7,8,9}, 1<= i <=9, sowie a10 Element von
> {0,1,2,3,4,5,6,7,8,9,X}, wobei X für den Wert 10 steht.
> Eine ISBN-Nummer ist korrekt, genau dann, wenn
> [mm]\summe_{i=1}^{10}[/mm] i*a= 0mod11 gilt. Überprüfen Sie die
> Gültigkeit dieser Gleichung! Konstruieren Sie einen
> endlichen Automaten, der genau die korrekten ISBN-Nummern
> akzeptiert!
> Hallo liebe Alle
>
> Ich zerbreche mir nun seit zwei Wochen den Kopf über den zu
> konstruierenden Automaten und finde keinen Ansatz. Ich habe
> mir gedacht, dass man den Automaten etwa so schreiben
> könnte:
>
> ->start --> s1 --> s2 --> s3 --> s4 --> s5 --> s6 --> s7
> --> s8 --> s9 --> s10 --> s11
> dabei sind die Übergänge von s1 bis s9 durch die Ziffern
> (0,1,2,3,4,5,6,7,8,9) herbeiführbar
> der Übergang von s9 zu s10 durch (0,1,2,3,4,5,6,7,8,9,X)
> und der Übergang von s10 zu s11 durch die 0, wenn die
> Berechnung des Modulo11=0 ergeben hat.
Wie willst du denn hier überhaupt das mod 11 mit einbringen? Bzw. die Summe? Und meinst du eigentlich vielleicht [mm] \sum_{i=1}^{10}i*a_i? [/mm] Was soll ansonsten das a sein?
> Mein Problem dabei ist: Der Automat kann sich ja eigentlich
> "nichts merken". Also weiß er ja am Ende auch nicht, welche
> Ziffern vor dem erreichten Zustand eingegeben wurden. Somit
> ist eine Berechnung auch nicht möglich.
Wieso, berechnen kannst du das doch in jedem Schritt. Aber das mit dem Zählen fand ich auch problematisch. Ich habe mir folgendes überlegt:
Du nimmst einen Startzustand plus 11 "normale" Zustände. Diese normalen Zustände nennst du [mm] z_0,...,z_{10} [/mm] und Zustand [mm] z_0 [/mm] bedeutet, dass die derzeitige Summe 0mod11 ist. Wenn du also z. B. gerade vom Startzustand mit einer 0 dorthin gegangen bist oder vllt nach 3 Zuständen die Zahlen 1,5,5 gegangen bist. Also allgemein bedeutet Zustand [mm] z_i, [/mm] dass die aktuelle Summe i mod 11 ist. Verständlich?
Das heißt, wenn du die Zustände [mm] z_0,...,z_{10} [/mm] im Kreis anordnest und den Startzustand in die Mitte schreibst, erhältst du für das erste mögliche Zeichen einen Stern, also vom Startzustand geht ein Pfeil zu jedem Zustand.
Ok. Dann könntest du dir für das zweite Zeichen überlegen: wenn das zweite Zeichen eine 0 ist, dann bleibt die bisherige Summe gleich. Das heißt, du zeichnest eine "Schleife", von jedem Zustand wieder zu sich selbst. Ist das zweite Zeichen eine 1, so wird in der Summe 2*1 addiert, das heißt, es geht von jedem Zustand 2 Zustände weiter. Bei einer 2 entsprechend 2*2=4 usw..
Das Ganze wird ziemlich komplex (gibt es da vllt besonders viele Punkte für die Aufgabe? Oder ist es gar eine Zusatzaufgabe?), und das Problem mit der Anzahl der Zeichen haben wir auch noch nicht gelöst.
Ich habe mir gerade für nur 3 Zeichen mal folgendes überlegt:
Bei jedem Übergang gibt es zwei Zeichen, und zwar gibt das erste Zeichen an, das wievielte Zeichen der ISBN jetzt dran ist und das zweite Zeichen gibt den "normalen" Übergang an. Das heißt, wenn wir im Startzustand sind, kann das erste Zeichen nur eine 1 sein. Jetzt machen wir aber erstmal wieder das Gleiche wie gerade: zu jedem Zustand einen Pfeil mit dem entsprechenden Zeichen, also mit der 0 zu Zustand [mm] z_0 [/mm] usw., allerdings schreiben wir da jetzt nicht eine 0, sondern 10 dran (die 1 steht ja gerade dafür, dass es die erste Zahl der ISBN ist). Nun haben wir also unsere erste ISBN und jetzt kommt die zweite, das heißt, die erste Ziffer des Übergangs wird eine 2 sein, für die zweite ist wieder alles möglich. Mit 21 gehen wir z. B. von jedem Zustand 2*1=2 Zustände weiter, mit 25 gehen wir 2*5=10 Zustände weiter, also quasi einen zurück usw.. Auch das wird sicher recht komplex, mit drei Zuständen hält es sich in Grenzen.
So, und jetzt kommt das Ende, dafür müssen wir noch einen Endzustand hinzufügen. Wenn wir 9 ISBN-Ziffern haben, wird die Beschriftung an unserem Übergangspfeil dreistellig, weil ja jetzt die 10te Ziffer kommt, also steht anfangs schon mal 10. Wenn wir uns nun z. B. in Zustand [mm] z_0 [/mm] befinden, wie auch immer wir dort hingekommen sind, dann kommen wir mit 100 in den akzeptierten Endzustand, denn dann müssen wir ja 0*10=0 addieren. Und da wir ja jetzt schon bei 0 mod 11 sind, bleiben wir auch da, wenn wir noch 0 addieren.
Nächstes Beispiel: wir sind nach 9 Ziffern in Zustand [mm] z_4, [/mm] haben also bisher 4 mod 11 als Summe, es fehlen also noch 7, damit wir auf 0 mod 11 kommen. 18 tun's auch, oder auch 29 oder 40 usw.. Wir kämen von [mm] z_4 [/mm] also z. B. mit einer 4 in den akzeptierten Endzustand, denn 4+40*4=44=0 mod 11.
Klar?
Wie gesagt, für 10 Ziffern wird das sicher sehr komplex, bei drei Ziffern hielt sich das mit dem Endzustand auch noch in Grenzen.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
|
