Deterministischer endlicher Automat (DEA)

Ello45

Mitglied
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.

Java:
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;
      
      
}
}
 
K

kneitzel

Gast
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

Top Contributor
Hey Ello45,

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

Beste Grüße,
Jar
 

Ello45

Mitglied
imag0702.jpg

Danke schonmal im Vorraus :)
 

Ello45

Mitglied
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

Top Contributor
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.
Java:
    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

Mitglied
Hab das ganze jetzt mal aufstellt aber was nun ?
Java:
      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

Administrator
Mitarbeiter
Du brauchst jetzt noch ne Methode die so ungefähr aussieht:
Java:
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;
}
 

Flown

Administrator
Mitarbeiter
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

Mitglied
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.... ?
 
Zuletzt bearbeitet:

Ello45

Mitglied
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)


Java:
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");
 

Bitfehler

Bekanntes Mitglied
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

Top Contributor
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

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

Java:
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

Java:
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.

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

Ello45

Mitglied
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
 
Zuletzt bearbeitet:

klauskarambulut

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

Java:
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)));
    }
}
 

Ello45

Mitglied
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

Bekanntes Mitglied
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

Top Contributor
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.
 

Ähnliche Java Themen

Neue Themen


Oben