www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Formale Sprachen" - Automat erstellen
Automat erstellen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Automat erstellen: Aufgabe 11
Status: (Frage) reagiert/warte auf Reaktion Status 
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

        
Bezug
Automat erstellen: Antwort
Status: (Antwort) fertig Status 
Datum: 22:37 Di 11.11.2008
Autor: Bastiane

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]

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de