# Deterministischer endlicher Automat (DEA)



## Ello45 (7. Jan 2016)

Hallo Leute,
ich habe vor einen DEA zu programmieren, dieser soll überprüfen ob ein vorgegebenes Eingabewort korrekt ist und dann ein Ergebnis ausgibt.

Die Eingabe und Ausgabe soll mitHilfe der Klasse JoptionPane stattfinden. Mögliche Eingabezeichen sind [ T , + , 8 , q ]

Die übergänge hab ich unten im Quelltext aufgeschreiben.

Wenn Zustand 4 erreicht wird soll am ende das wort richtig erscheinen und wenn nicht dann falsch.

Z.b bei q88q soll falsch rauskommen und bei +T+q richtig 

Ich Hoffe ihr könnt mir weier helfen 

Ich habe schon ein bisschen vorgearbeiten, habe jedoch keine Ahnung  wie ich jetzt weiter komme.


```
import javax.swing.JOptionPane;

public class DEA14 {
public static void main(String[] args) {
     
        //Eingabe des Eingabewortes
        String eingabe1 = JOptionPane.showInputDialog("Eingabewort:");
        //Test
        System.out.println("Eingabewort: " +eingabe1);
      
    
        //Teilen des Eingabewortes in einzelne Zeichen
        String[]word = eingabe1.split("");
        //Test
        System.out.println("Zeichen 1: "+word[0]);
        System.out.println("Zeichen 2: "+word[1]);
        System.out.println("Zeichen 3: "+word[2]);
        System.out.println("Zeichen 4: "+word[3]);
      
        //Übergänge festlegen
        int [ ][ ] uebergaenge = new int[5][128];
     
        //Zustand 0 Übergänge
        uebergaenge[0]['T'] = 0;
        uebergaenge[0]['+'] = 1;
        uebergaenge[0]['8'] = 3;
        uebergaenge[0]['q'] = 1;
      
        //Zustand 1 Übergänge
        uebergaenge[1]['T'] = 3;
        uebergaenge[1]['+'] = 1;
        uebergaenge[1]['8'] = 1;
        uebergaenge[1]['q'] = 3;
      
        //Zustand 2 Übergänge
        uebergaenge[2]['T'] = 1;
        uebergaenge[2]['+'] = 4;
        uebergaenge[2]['8'] = 2;
        uebergaenge[2]['q'] = 4;
      
        //Zustand 3 Übergänge
        uebergaenge[3]['T'] = 3;
        uebergaenge[3]['+'] = 2;
        uebergaenge[3]['8'] = 2;
        uebergaenge[3]['q'] = 2;
      
        //Zustand 4 Übergänge
        uebergaenge[4]['T'] = 4;
        uebergaenge[4]['+'] = 4;
        uebergaenge[4]['8'] = 4;
        uebergaenge[4]['q'] = 4;
      
      
}
}
```


----------



## Flown (7. Jan 2016)

Wo liegt denn dein Problem, was ist denn deine Frage?


----------



## kneitzel (7. Jan 2016)

Also das zweidimensionale Array mit 128 Spalten halte ich für heftig, wenn nur 4 benutzt werden. Hier würde ich Konstanten erstellen für die erlaubten Zeichen mit 0,1,2 und 3 und das dann halt anpassen.

Und Deine Implementation der Übergänge verstehe ich im Augenblick nicht ganz. Was bedeutet da das Array genau? Oder habe ich die Beschreibung übersehen?

Konrad


----------



## Jardcore (7. Jan 2016)

Hey Ello45,

könntest du vielleicht ein Modell deines Automaten zeigen. Vielleicht gibt es dort ein Problem.

Beste Grüße,
Jar


----------



## Ello45 (7. Jan 2016)

Danke schonmal im Vorraus


----------



## Flown (7. Jan 2016)

Was ist jetzt deine Frage? Bei was brauchst du hilfe?


----------



## Ello45 (7. Jan 2016)

_Ich hab ja schonmal probiert anzufangen den Quellcode zu schreiben für cen Automat.
Was muss ic denn jezt noch machen dass der meine Eingabe überprüft und dann am ende ein richtig oder falsch rauskommt_


----------



## Jardcore (7. Jan 2016)

Ich würde das wahrscheinlich ein wenig anders Modellieren. Und zwar könnte man eine neue Klasse *State *(Zustand) und eine Klasse *Transition *(Übergang) erstellen. Die Transition erbt hierbei von HashMap<Character, State> und wäre ein Attribut von State.

Die State Klasse bekommt dann noch zwei Methoden, eine für das Hinzufügen einer Transition und eine andere für das Zurückgeben eines Zustandes abhängig vom Eingabezeichen.

Das ganze wäre dann auch objektorientiert 

Die Main würde dann in etwa so aussehen.

```
public static void main(String[] args) {
        State z0 = new State();
        State z1 = new State();
        State z2 = new State();
        State z3 = new State();
        State z4 = new State();
    
        z0.addTransition('T', z0);
        z1.addTransition('T', z3);
        //...
    
        // Logik zum Durchlaufen der Transition
        //for(char c : ...) {
        //    if(z4.getNextState(c) == z4) {
        //    }
    }
```


----------



## Ello45 (7. Jan 2016)

Hab das ganze jetzt mal aufstellt aber was nun ? 

```
public static void main(String[] args) {
            State z0 = new State();
            State z1 = new State();
            State z2 = new State();
            State z3 = new State();
            State z4 = new State();
       
            z0.addTransition('T', z0);
            z0.addTransition('+', z1);
            z0.addTransition('8', z3);
            z0.addTransition('q', z1);
            z1.addTransition('T', z3);
            z1.addTransition('+', z1);
            z1.addTransition('8', z1);
            z1.addTransition('q', z3);
            z2.addTransition('T', z1);
            z2.addTransition('+', z4);
            z2.addTransition('8', z2);
            z2.addTransition('q', z4);
            z3.addTransition('T', z3);
            z3.addTransition('+', z2);
            z3.addTransition('8', z2);
            z3.addTransition('q', z2);
            z4.addTransition('T', z4);
            z4.addTransition('+', z4);
            z4.addTransition('8', z4);
            z4.addTransition('q', z4);
```


----------



## Flown (7. Jan 2016)

Du brauchst jetzt noch ne Methode die so ungefähr aussieht:

```
public boolean checkForInput(String input) {
   State cur = start;
   for (int i = 0; i < input.length(); i++) {
     cur = cur.translate(input.charAt(i));
   }
   return cur == end;
}
```


----------



## Ello45 (7. Jan 2016)

Könntest du mir die Methode ein wenig aufschlüseln?


----------



## Flown (7. Jan 2016)

Du startest bei deinem Startelement. Da du ja einen String angibst welches dein Wort darstellt, gehst du transition für transition durch und siehst überprüfst ob du bei deinem Endelement angelangt bist. Fertig.


----------



## Ello45 (7. Jan 2016)

Mir fällt jetzt auch gerade auf , dass sobald der Zustand Z4 einmal erricht ist sich der nicht mehr ändert , weil egal was danch für ein zeichen kommt es bleibt in Z4 also muss die Methode ja nur noch stoppen sobald einmal der Stuts Z4 erreicht ist und dann das ausgabewort geben.

DANKE! 

update: kann man da nicht iegndwass wie if state = z4  system.out.println.... ?


----------



## Jardcore (7. Jan 2016)

Guck dir mal mein if an  das macht das... das print fehlt nurnoch


----------



## Ello45 (7. Jan 2016)

Jetzt verlier ich wirklich die Übersicht

Exception in thread "main" java.lang.Error: Unresolved compilation problems: 
    State cannot be resolved to a type
    State cannot be resolved to a type
    State cannot be resolved to a type
    State cannot be resolved to a type
    State cannot be resolved to a type
    State cannot be resolved to a type
    State cannot be resolved to a type
    State cannot be resolved to a type
    State cannot be resolved to a type
    State cannot be resolved to a type
    c cannot be resolved to a variable

    at DEA14.main(DEA14.java:22)



```
import javax.swing.JOptionPane;

public class DEA14 {
public static void main(String[] args) {
      
        //Eingabe des Eingabewortes
        String eingabe1 = JOptionPane.showInputDialog("Eingabewort:");
        //Test
        System.out.println("Eingabewort: " +eingabe1);
       
     
        //Teilen des Eingabewortes in einzelne Zeichen
        String[]word = eingabe1.split("");
        //Test
        System.out.println("Zeichen 1: "+word[0]);
        System.out.println("Zeichen 2: "+word[1]);
        System.out.println("Zeichen 3: "+word[2]);
        System.out.println("Zeichen 4: "+word[3]);
       
       //Übergänge festlegen
       
                  State z0 = new State();
                  State z1 = new State();
                  State z2 = new State();
                  State z3 = new State();
                  State z4 = new State();
            
                  z0.addTransition('T', z0);
                  z0.addTransition('+', z1);
                  z0.addTransition('8', z3);
                  z0.addTransition('q', z1);
                  z1.addTransition('T', z3);
                  z1.addTransition('+', z1);
                  z1.addTransition('8', z1);
                  z1.addTransition('q', z3);
                  z2.addTransition('T', z1);
                  z2.addTransition('+', z4);
                  z2.addTransition('8', z2);
                  z2.addTransition('q', z4);
                  z3.addTransition('T', z3);
                  z3.addTransition('+', z2);
                  z3.addTransition('8', z2);
                  z3.addTransition('q', z2);
                  z4.addTransition('T', z4);
                  z4.addTransition('+', z4);
                  z4.addTransition('8', z4);
                  z4.addTransition('q', z4);
       
        if(z4.getNextState(c) == z4) System.out.println("bestanden");
```


----------



## VfL_Freak (7. Jan 2016)

Moin,

'State' ist nicht bekannt!
Entweder importieren oder eine entsprexchencde Klasse anlegen !

Gruß Klaus


----------



## Bitfehler (7. Jan 2016)

Ello45 hat gesagt.:


> Mir fällt jetzt auch gerade auf , dass sobald der Zustand Z4 einmal erricht ist sich der nicht mehr ändert , weil egal was danch für ein zeichen kommt es bleibt in Z4 also muss die Methode ja nur noch stoppen sobald einmal der Stuts Z4 erreicht ist und dann das ausgabewort geben.
> 
> DANKE!
> 
> update: kann man da nicht iegndwass wie if state = z4  system.out.println.... ?



Ich glaube, dass ist nicht ganz korrekt.
Prinzipiell kann der Automat ewig in dem Zustand Z4 bleiben ohne die Eingabe abgearbeitet zu haben. Würdest du gleich beim ersten Erreichen von Z4 aufhören, ist der Fall, dass die Eingabe ein ungültiges Zeichen enthält nicht abgedeckt. Dein Programm würde sagen, alles wäre ok, obwohl der Automat die Eingabe nicht abdeckt (oder es soll ist ein Übergang getätigt werden, der von Z4 wegführt, obwohl es keine Überführung gibt.).

(So ganz sicher bin ich mir nicht, das war nie mein Lieblingsthemengebiet)


----------



## Jardcore (8. Jan 2016)

Ello45 hat gesagt.:


> Exception in thread "main" java.lang.Error: Unresolved compilation problems:
> State cannot be resolved to a type


Du solltest nicht einfach irgendwas abkopieren... du musst auch schon die Klassen erstellen... oO
Würde dir empfehlen eine Klasse *State*, eine Klasse *Transitions *und eine Klasse *Dea *anzulegen.

In Dea kannst du dann auch den von Bitfehler angesprochenen Fehler gut abarbeiten.


----------



## klauskarambulut (8. Jan 2016)

So kann man z.B. die Zustände definieren


```
package spielwiese.statemachine;

public enum State {
    Z0 {

        @Override
        public State transit(String ch) {
            if(ch.equals("T")) {
                return Z0;
            }
            if(ch.equals("+")) {
                return Z1;
            }
            if(ch.equals("8")) {
                return Z3;
            }
            if(ch.equals("q")) {
                return Z1;
            }
            throw new IllegalArgumentException();
        }
       
    }, Z1 {

        @Override
        public State transit(String ch) {
            if(ch.equals("T")) {
                return Z3;
            }
            if(ch.equals("+")) {
                return Z1;
            }
            if(ch.equals("8")) {
                return Z1;
            }
            if(ch.equals("q")) {
                return Z3;
            }
            throw new IllegalArgumentException();
        }
   
    },Z2 {

        @Override
        public State transit(String ch) {
            if(ch.equals("T")) {
                return Z1;
            }
            if(ch.equals("+")) {
                return Z4;
            }
            if(ch.equals("8")) {
                return Z2;
            }
            if(ch.equals("q")) {
                return Z4;
            }
            throw new IllegalArgumentException();
        }
   
    }, Z3{

        @Override
        public State transit(String ch) {
            if(ch.equals("T")) {
                return Z3;
            }
            if(ch.equals("+")) {
                return Z2;
            }
            if(ch.equals("8")) {
                return Z2;
            }
            if(ch.equals("q")) {
                return Z2;
            }
            throw new IllegalArgumentException();
        }
   
    },Z4{

        @Override
        public State transit(String ch) {
            if(ch.equals("T")) {
                return Z4;
            }
            if(ch.equals("+")) {
                return Z4;
            }
            if(ch.equals("8")) {
                return Z4;
            }
            if(ch.equals("q")) {
                return Z4;
            }
            throw new IllegalArgumentException();
        }   
    };
   
    public abstract State transit(String ch);
}
```

So kann man dann die Wörter checken


```
package spielwiese.statemachine;

import java.util.stream.Stream;

public class DEA14 {

    public static void main(String[] args) {
        Stream.of("q88q", "+T+q", "+T8q", "+8+q", "88q+", "qq8T")
                .forEach(word -> System.out.println(word + ": " + check(word)));
    }

    public static boolean check(String word) {
        State current = State.Z0;

        for (String ch : word.split("")) {
            current = current.transit(ch);
        }
        return current == State.Z4;
    }
}
```

Alles klar?! Alles klar.


```
q88q: false
+T+q: true
+T8q: true
+8+q: false
88q+: true
qq8T: false
```


----------



## Ello45 (8. Jan 2016)

Du bist ein Held   
würde jedoch gerne die überprüfung so abändern ,dass die eingaewörter nicht schon da fest stehen sondern per dialogfenster eingegen werden  aber kommt uach noch  vielen dank


----------



## klauskarambulut (8. Jan 2016)

Und wenn es etwas minimalistischer sein soll, dann geht das auch so


```
package spielwiese.statemachine;

import java.util.stream.Stream;

public class DEA14 {

    private final String alphabet;
    private final int[][] transitions;
    private final int start;
    private final int end;

    public DEA14(String alphabet, int[][] transitions, int start, int end) {
        this.alphabet = alphabet;
        this.transitions = transitions;
        this.start = start;
        this.end = end;
    }

    public boolean check(String word) {
        int currentState = start;

        for (String ch : word.split("")) {
            int chPosition = alphabet.indexOf(ch);
            currentState = transitions[currentState][chPosition];
        }
        return currentState == end;
    }

    public static void main(String[] args) {

        String alphabet = "T+8q";

        int[][] transitions = new int[][]{
            {0, 1, 3, 1},
            {3, 1, 1, 3},
            {1, 4, 2, 4},
            {3, 2, 2, 2},
            {4, 4, 4, 4}
        };

        DEA14 dea14 = new DEA14(alphabet, transitions, 0, 4);

        Stream.of("q88q", "+T+q", "+T8q", "+8+q", "88q+", "qq8T")
                .forEach(word -> System.out.println(word + ": " + dea14.check(word)));
    }
}
```


----------



## Jardcore (8. Jan 2016)

... Lösungen posten 



klauskarambulut hat gesagt.:


> *return* currentState == end;


Führt hier zu einem Fehler wenn man Beispielsweise "Hallo" eingibt. Wurde auch schon weiter oben angesprochen.


----------



## Ello45 (8. Jan 2016)

Die Möglichkeit der falsch eingabe ist ja hier in dem fall erstmal nicht möglich da es nur 5 feste eigabewöter gibt und davon alle korrekt sind von der schreibeise. Danke euch aber auf jeden fall für eure Vorschläge


----------



## Bitfehler (8. Jan 2016)

Die beiden vorgeschlagenen Lösungen decken dennoch einen Fall nicht ab.
Eine gültige Reihenfolge laut Aufgabe ist 88q+.
Z0 über 8 nach Z3
Z3 über 8 nach Z2
Z2 über q nach Z4
Z4 über + nach Z4

Bei dem Vergleich wird aber aber der Endzustand nach der q-Transition erreicht und es wird abgebrochen ohne das Plus zu lesen. Das erscheint mir inkorrekt, da zwar ein Endzustand erreicht wird, die Folge aber nicht abgearbeitet wurde, auch wenn man den Zustand nicht verlässt.


----------



## Jardcore (9. Jan 2016)

Der von klauskarambulut gepostete Vorschlage sollte das eigentlich richtig durcharbeiten.
Dort wird jeden Wort in die Check Methode gegeben und dort wiederum jeder Buchstabe durchiteriert.
Wenn alle angeschaut wurden wird erst geprüft ob der letzte Zustand auch der Endzustand ist... also eigentlich sollte auch 88q+ eindeutig aufgelöst werden können.


----------



## Vespulaa (13. Jan 2017)

Was ist denn nun das Ergebnis?
Komme von allein nicht auf den fertigen Quellcode


----------



## VfL_Freak (13. Jan 2017)

Moin,


Vespulaa hat gesagt.:


> Was ist denn nun das Ergebnis?
> Komme von allein nicht auf den fertigen Quellcode


Dir ist schon klar, das dies Thema älter als ein Jahr ist ?? 
Mach einfach ein neues Thema auf, poste was Du hast und stell' dann konkrete Fragen dazu !!
Gruß Klaus


----------

