"Christmas - the time to fix the computers of your loved ones" « Lord Wyrm

Endlicher Automat

SeVen 07.11.2015 - 11:17 7307 45 Thread rating
Posts

SeVen

Little Overclocker
Registered: Apr 2006
Location: Germany
Posts: 96
Hallo,

ich möchte einen endlichen Automaten programmieren und weiß nicht so recht wie ich starten soll.
Es soll eine Kommazahl mit eventuellem Vorzeichen eingegeben werden wie z.B. : +34,56 oder - 1,234 oder 2,55. Dieser soll erkennen ob diese Zahl eine Kommazahl ist.

Ich habe 8 Zustände:

1. Startzustand 0
2. Vorzeichen wurde eingegeben
3. Vorzeichen + Zahl wurde eingegeben
4. Vorzeichen + Zahl + Komma wurde eingegeben
5. Kommazahl (Endzustand)
6. Zahl wurde eingegeben
7. Zahl + Komma wurde eingegeben
8. Fehlerzustand

Die Tabelle dazu:

SeVen

Little Overclocker
Registered: Apr 2006
Location: Germany
Posts: 96
Ich habe angefangen meine Zustände zu initialisieren und weiß ich nicht wie ich starten soll... Ich möchte es gerne über arrays lösen. Vielleicht mit Switch case...?

SeVen

Little Overclocker
Registered: Apr 2006
Location: Germany
Posts: 96
Ich bin so gestartet und weiß gerade nicht wie ich von einem Zustand in den nächste komme. Es muss ja jedes Zeichen das eingegeben wurde nacheinander überprüft werden. Wie kann ich sagen, wenn du in Zustand 1 bist und das nächste Zeichen kommt, versetzte dich in Zustand 2 z.B. ?

-=Willi=-

The Emperor protects
Avatar
Registered: Aug 2003
Location: ~
Posts: 1624
Ich hab zwar grad keine Zeit dir zu helfen aber nimm lieber die [code]-Tags oder pastebin.com wenn du Code herzeigen willst ;).

Denne

Here to stay
Avatar
Registered: Jan 2005
Location: Germany
Posts: 2801
Sind das eigentlich deine Hausaufgaben? :D

SeVen

Little Overclocker
Registered: Apr 2006
Location: Germany
Posts: 96
Ich muss es für mein Studium machen!
Habe es eigentlich fertig, leider gibt er nicht das richtige raus :(
Kann ich um das nächste Zeichen zu untersuchen überhaupt schreiben:
zeile [i] + 1 oder bekomme ich damit gar nicht das nächste Zeichen?
Vielleicht liegt darin der Fehler.

Blaues U-boot

blupp, blupp
Avatar
Registered: Aug 2005
Location: Graz
Posts: 1541
der unterschied zwischen zeile[i]+1 und zeile[i+1] ist essentiell.
schau dir bitte nochmal an, wie man arrays behandelt.

charmin

Super Moderator
10x
Avatar
Registered: Dec 2002
Location: aut_sbg
Posts: 14585
Seven bitte kopier den code rein, mit bildern is das sehr umständlich. Nimm bitte die code tags her.

SeVen

Little Overclocker
Registered: Apr 2006
Location: Germany
Posts: 96
Code:
int i;
     char []zeile; char c;
     zeile = IO.readChars("Bitte geben Sie eine Kommazahl ein: ");
     int Zustand = 0;

       for( i = 0; i < zeile.length; i++){
         c = zeile [i];

         if( c == '+'){
           Zustand = 1;
         }
         else if( c == '-'){
           Zustand = 1;
         }
         else if( (int)c - (int)'0' >= 0){
           Zustand = 5;
         }
         else{
           Zustand = 7;
         }

         int nextZahl = zeile [i] + 1;

         switch (Zustand){
           case 1:
             if( nextZahl == (int)c - (int)'0' ){
               Zustand = 2;
             }
             else{
               Zustand = 7;
             }
             break;
           case 5:
             if( nextZahl == (int)c - (int)'0' ){
               Zustand = 5;
             }
             else if ( nextZahl == ',' ){
               Zustand = 6;
             }
             else{
               Zustand = 7;
             }
             break;
}
             nextZahl = nextZahl ++;

         switch (Zustand){
           case 2:
             if( nextZahl == (int)c - (int)'0' ){
               Zustand = 2;
             }
             else if( nextZahl == ',' ){
               Zustand = 3;
             }
             else{
               Zustand = 7;
             }
             break;
           case 6:
             if( nextZahl == (int)c - (int)'0'){
               Zustand = 4;
             }
             else{
               Zustand = 7;
             }
         }
             nextZahl = nextZahl ++;

         switch (Zustand){
           case 3:
             if( nextZahl == (int)c - (int)'0' ){
               Zustand = 4;
             }
             else{
               Zustand = 7;
             }
             break;
           case 4:
             if( nextZahl == (int)c - (int)'0' ){
               Zustand = 4;
             }
             else{
               Zustand = 7;
             }
         }
       }
             if( Zustand == 4) {
 IO.println( "Die Zahl ist eine Kommazahl!");
             }
             else{
               IO.println( "Die Zahl ist keine Kommazahl!");
             }
  }
}

SeVen

Little Overclocker
Registered: Apr 2006
Location: Germany
Posts: 96
Ich habe es probiert mit [i + 1]. Das Problem ist das er natürlich irgendwann außerhalb des arrays ist. Gibt es dafür einen Befehl das er nur bis zum Ende des eigegebenen arrays vorgeht?

SeVen

Little Overclocker
Registered: Apr 2006
Location: Germany
Posts: 96
Vestehe ich das richtig wenn ich innerhalb des arrays also [i+1] schreibe geht er ein Zeichen weiter. Wenn ich aber [i] + 1 schreibe wird der Wert in an der Stelle i um 1 erhöht?

SeVen

Little Overclocker
Registered: Apr 2006
Location: Germany
Posts: 96
Habe es so nochmal versucht. Gibts es keine Möglichkeit das ich meine Variable nextZahl auf das nächste Zeichen setzten kann? Oder ist der komplette Ansatz falsch?

Code:
int i;
     char []zeile; char c;
     zeile = IO.readChars("Bitte geben Sie eine Kommazahl ein: ");
     int Zustand = 0;

       for( i = 0; i < zeile.length; i++){ // Eingabe durchlaufen
         c = zeile [i]; // erstes Zeichen = c

         if( c == '+'){ // Überprüfung auf Vorz. und ggf. auf Zustand 1 setzten
           Zustand = 1;
         }
         else if( c == '-'){
           Zustand = 1;
         }
         else if( (int)c - (int)'0' >= 0){ // Überprüfung auf Zahl -> Zust. 5 
           Zustand = 5;
         }
         else{ // wenn kein Vorzeichen oder Zahl Zustand auf 7 setzten 
           Zustand = 7;
         }

         int nextZahl;
         nextZahl = zeile [0];

         switch (Zustand){
           case 1:
             if( nextZahl == (int)c - (int)'0' ){
               Zustand = 2;
             }
             else{
               Zustand = 7;
             }
             break;
           case 5:
             if( nextZahl == (int)c - (int)'0' ){
               Zustand = 5;
             }
             else if ( nextZahl == ',' ){
               Zustand = 6;
             }
             else{
               Zustand = 7;
}
             break;
         }
             nextZahl = zeile [2];

         switch (Zustand){
           case 2:
             if( nextZahl == (int)c - (int)'0' ){
               Zustand = 2;
             }
             else if( nextZahl == ',' ){
               Zustand = 3;
             }
             else{
               Zustand = 7;
             }
             break;
           case 6:
             if( nextZahl == (int)c - (int)'0'){
               Zustand = 4;
             }
             else{
               Zustand = 7;
             }
         }
             nextZahl = zeile [3];

         switch (Zustand){
           case 3:
             if( nextZahl == (int)c - (int)'0' ){
               Zustand = 4;
             }
             else{
               Zustand = 7;
             }
             break;
           case 4:
             if( nextZahl == (int)c - (int)'0' ){
               Zustand = 4;
             }
             else{
               Zustand = 7;
             }
}
       }
             if( Zustand == 4) {
               IO.println( "Die Zahl ist eine Kommazahl!");
             }
             else{
               IO.println( "Die Zahl ist keine Kommazahl!");
             }
  }
}

tinker

SQUEAK
Avatar
Registered: Nov 2005
Location: NÖ
Posts: 5222
Ich fang mal ganz vorne an:

Meiner Meinung nach hast du zu viele Zustände. Du musst eigentlich nicht zwischen "Vorzeichen + Zahl" und "Zahl" unterscheiden, sind beides Zahlen und ob sie jetzt ein Vorzeichen haben is für deinen Anwendungsfall egal und sollte vom Automaten auch nicht abgebildet werden. Gleiches gilt für "Vorzeichen + Zahl + Komma" und "Zahl + Komma".

Sonst schaut die Übergangstabelle gut aus.

Deinen Programmansatz find ich dann aber etwas wirr... Vor allem versteh ich den Sinn der Variable nextZahl nicht, und warum du innerhalb der Schleife mit nem festen Index auf das zeile-Array zugreifst ("nextZahl = zeile [2];").

Ich schlag mal einen anderen Ansatz vor (auch wenn ich EAs bisher nur formal definiert hab, also gut möglich, dass es auch besser geht):

Fürs Programm würde ich die Übergangstabelle als 2d Array speichern. Zeilenindex ist der Zustand und Spaltenindex ist das Eingabealphabet.

Damit hast du mal die Zustände und das Eingabealphabet definiert. Dann fehlt noch die Übergangsfunktion. Da gehts ja darum durch die Verbindung aus einem Zustand und einer Eingabe wieder zu einem Zustand zu kommen. Und das kannst du ja einfach aus deiner Übergangstabelle auslesen.

In der Variable "zeile" hast du ja schon dein Eingabearray gespeichert. Jetzt würde ich noch ein zweites array für die Zustände erstellen, das gleich lang ist. (* bzw. reicht eigentlich auch eine einfache Zustandsvariable, siehe EDIT unten)

Und dann musst du nur das Eingabearray nach der Reihe durchgehen und für das aktuelle Zeichen (i) den letzten Zustand (i-1) aus dem Zustandsarray auslesen. Mit den beiden Werten kannst du dir dann einfach den nächsten Zustand aus einer Übergangstabelle holen (du musst für ein Zeichen natürlich noch den passenden Spaltenindex finden). Ein Sonderfall ist natürlich das Auslesen des ersten Zeichens aus deinem Eingabearray, da es dafür keinen Zustand in deinem Zustandarray gibt. Aber den Fall kannst du ja einfach abdecken.

Kurzes Beispiel wies dann in etwa ausschaut:
ea_208637.png

Und wenn der letzte Zustand im Zustandsarray ein Endzustand ist, hat der Automat die Eingabe akzeptiert.

EDIT: Wobei, das mit dem Zustandsarray muss eigentlich nicht sein. Du kannst das auch mit einer einfachen Zustandsvariable machen. Mit 0 initialisieren, mit dem ersten Zeichen aus dem Eingabearray vergleichen und neuen Zustand aus der Übergangstabelle in die Zustandsvariable schreiben. Dann nächstes Zeichen mit dem Zustand vergleichen, wieder neuen Zustand aus Übergangstabelle schreiben usw. Wenn die Zustandsvariable am Ende den Wert wert eines Endzustands hat, hat der Automat akzeptiert.
Bearbeitet von tinker am 07.11.2015, 22:34

SeVen

Little Overclocker
Registered: Apr 2006
Location: Germany
Posts: 96
Vielen Dank für die Antwort, dann lag ich doch eher auf dem Holzweg.
Ich habe jetzt so angefangen:

Code:
int[][] Zustaende = { {1,7,5}, 
                           {7,7,2},
                           {7,3,2},
                           {7,7,4},
                           {7,7,4},
                           {7,6,5},
                           {7,7,4},
                           {7,7,7} }
     int i;
     char[] zeile; char c;
     zeile = IO.readChars( "Bitte geben Sie eine Kommazahl ein: ");

SeVen

Little Overclocker
Registered: Apr 2006
Location: Germany
Posts: 96
Leider vestehe ich nicht wie ich nacheinander das Eingabearray mit den Zuständen vergleichen kann.
Kontakt | Unser Forum | Über overclockers.at | Impressum | Datenschutz