Modélisation d'un déterministes Finite Automaton par ces données

Question

J'ai ce fichier d'entrée:

2 
3 2 1 
ab 
1 0 
2 0 
2 0 
2 
0 3 
abaa 
aab 
aba 
3 3 2 
ade 
0 1 2 
1 2 0 
2 1 0 
1 2 
2 2 
a 
de 

La première ligne représente le nombre de cas de test.

Chaque cas de test commence par 3 entiers, le premier est le nombre d'états pour l'automate, ensuite le nombre de symboles dans l'alphabet, puis le nombre d'états finaux.

La ligne suivante est l'alphabet. Les symboles apparaissent ensemble.

Ensuite, il y a un nombre de lignes égal au nombre d'états qui décrivent la fonction de transition. La première ligne de ce groupe de lignes représente la fonction de transition pour le premier état de l'automate (qo), le premier élément représente l'état atteint lorsque le premier symbole de l'alphabet passe à cet état, et ainsi de suite. J'ai eu du mal à comprendre cela à partir de l'énoncé du problème original. Ceci est la meilleure façon que je suis venu le voir:

Les lignes:

1 0 
2 0 
2 0 

égale:

  AlphabetSymbol0  AlphabetSymbol1 
State0   State1    State0 
State1   State2    State0 
State2   State2    State0 

Ensuite, il y a une ligne qui dit qui sont les états finaux de l'automate . Puis vient une ligne qui indique quel est l'état initial et combien de chaînes d'entrée viendront.

Puis viennent les lignes avec les chaînes d'entrée.

La sortie de ce programme devrait être:

Case #1: 
accept 2 
reject 0 
reject 1 
Case #2: 
accept 2 
reject 0 

Il faut dire que si la chaîne est acceptée ou rejetée et quel état il a fini. Jusqu'à présent, j'ai seulement codé le travail avec l'entrée.

Je ne sais pas comment serait plus commode de représenter l'automate. Devrais-je créer une classe Graph? Dois-je simplement utiliser des tableaux? Quelle logique appliquerais-je aux tableaux?

MODIFIER CECI EST LE CODE QUE J'AI PRODUIT À LA SUITE DU CONSEIL DE MICHAEL BORGWARDT. LES TRANSITIONS FONCTIONNENT MAIS JE NE SAIS PAS POURQUOI LA CORDE SE FAIT MÊCHER SUR L'ÉTAT 0 LORSQU'ELLE EST TRAITÉE. **

/* 
* To change this template, choose Tools | Templates 
* and open the template in the editor. 
*/ 

package afd; 

import java.io.*; 
import java.util.*; 

/** 
* 
* @author Administrator 
*/ 
public class Main { 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) throws IOException { 
     // TODO code application logic here 

     FileReader fr = new FileReader("E://Documents and Settings//Administrator//My Documents//NetBeansProjects//AFD//src//afd//dfa.in"); 


     BufferedReader br = new BufferedReader(fr); 

     String firstLine= br.readLine(); 


     String [] firstLineSplitted = firstLine.split(" "); 

     /*debug*/ 
     System.out.println("firstLine is " + firstLine); 

     int numberOfTestCases = Integer.parseInt(firstLine); 

     for (int indexOfTestCases =0; indexOfTestCases < numberOfTestCases; indexOfTestCases++ ){ 



      String caseStartLine = br.readLine(); 

      /*debug*/ 
      System.out.println("caseStarLine is " + caseStartLine); 
      String [] caseStartLineSplitted = caseStartLine.split(" "); 

      int numberOfStates; 
      int numberOfAlphabetSymbols; 
      int numberOfFinalStates; 


      numberOfStates = Integer.parseInt(caseStartLineSplitted[0]); 

      numberOfAlphabetSymbols = Integer.parseInt(caseStartLineSplitted[1]); 

      numberOfFinalStates = Integer.parseInt(caseStartLineSplitted[2]); 




      Automaton automaton = new Automaton(); 


      automaton.setAllStates(numberOfStates); 

    //   automaton.size = numberOfStates; 
//   automaton.numberOfAlphabetSymbols = numberOfAlphabetSymbols; 
//   automaton.numberOfFinalStates = numberOfFinalStates; 
      //Automaton a = new Automaton(numberOfStates); 


      String alphabetLine = br.readLine(); 
      System.out.println("alphabetLine is " + alphabetLine); 

      automaton.setAlphabet (alphabetLine); 

//   automaton.alphabetSymbols =new StringBuffer(alphabetLine); 

      for (int indexOfStates = 0; indexOfStates < numberOfStates; indexOfStates++){ 

        String transitionsLine = br.readLine(); 
        /*debug*/ 
        System.out.println("transitionsLine is " + transitionsLine); 

        automaton.setTransitions(indexOfStates,transitionsLine); 

        /*String [] ijLineSplitted = ijLine.split(" "); 

        int i = Integer.parseInt(ijLineSplitted[0]); 
        int j = Integer.parseInt(ijLineSplitted[1]); 
        */ 

      } 

      String finalStatesLine = br.readLine(); 
      /*debug*/ 
      System.out.println("finalStatesLine is " + finalStatesLine); 
      String finalStatesLineSplitted [] = finalStatesLine.split(" "); 

      automaton.markFinalStates(finalStatesLineSplitted); 



      String initialStateAndNumberOfStringsLine = br.readLine(); 

      /*debug*/ 
      System.out.println("initialStateAndNumberOfStringsLine is " +initialStateAndNumberOfStringsLine); 
      String [] splittedInitialStateLine = initialStateAndNumberOfStringsLine.split(" "); 

      int initialState = Integer.parseInt(splittedInitialStateLine[0]); 
      int numberOfStrings = Integer.parseInt(splittedInitialStateLine[1]); 

      automaton.markInitialState(initialState); 

      for (int stringIndex =0; stringIndex<numberOfStrings; stringIndex++){ 

       String stringToProcess = br.readLine(); 
       /*debug*/ 
      System.out.println("stringToProcess is " + stringToProcess); 

       automaton.processString(stringToProcess); 


      } 


     } 
     } 







} 


class State extends HashMap<Character, State>{ 

boolean isFinal; 
boolean isInitial; 

State() { 
    isInitial=false; 
    isFinal = false; 
    } 

} 

    class Automaton{ 
    List <State> allStates; 
    //private List<State> finalStates; 
    int theInitialStateIntIndex; 
    State currentState; 
     char [] alphabet; 




    Automaton() { 


     allStates = new ArrayList<State>(); 


    } 

    public void setAllStates (int numberOfStates) { 

     for (int i =0; i <numberOfStates; i++) { 

      State newState = new State(); 
      allStates.add(newState); 

     } 

    } 


    public void setAlphabet (String alphabetLine){ 

     alphabet = alphabetLine.toCharArray(); 




    } 

    public void markFinalStates (String [] finalStates){ 

     for (int index =0; index<finalStates.length; index++) { 

      int aFinalStateId = Integer.parseInt(finalStates[index]); 

      State aFinalState = allStates.get(aFinalStateId); 
      aFinalState.isFinal = true; 
      allStates.add(aFinalStateId, aFinalState); 


      /*DEBUG*/ 
      aFinalState = allStates.get(aFinalStateId); 
      if ((aFinalState.isFinal)==true) 
      System.out.println("THE STATE " + aFinalStateId + " IS MARKED AS FINAL"); 

     } 

    } 

    public void markInitialState (int initialStateId) { 

      State theInitialState = allStates.get(initialStateId); 
      theInitialState.isInitial=true; 
      allStates.add(initialStateId, theInitialState); 

      theInitialStateIntIndex = initialStateId; 

      /*DEBUG*/ 

      System.out.println("THE INITIAL STATE ID IS " + initialStateId); 

      theInitialState = allStates.get(initialStateId); 
      if ((theInitialState.isInitial)==true) 
      System.out.println("THE STATE " + initialStateId + " IS MARKED AS INITIAL"); 

    } 


    public void setTransitions(int stateId, String transitionsLine){ 


      State theOneToChange = allStates.get(stateId); 

      String [] statesToReachStringSplitted = transitionsLine.split(" "); 

      for (int symbolIndex=0; symbolIndex<statesToReachStringSplitted.length;symbolIndex++){ 

       int reachedState= Integer.parseInt(statesToReachStringSplitted[symbolIndex]); 

       theOneToChange.put(alphabet[symbolIndex],allStates.get(reachedState)); 

       System.out.println("THE STATE " + stateId + " REACHES THE STATE " + reachedState + " WITH THE SYMBOL " + alphabet[symbolIndex]); 

      } 

      allStates.add(stateId, theOneToChange); 

    } 


    public int findInitialState(){ 


     int index =0; 

     cycle: for (; index<allStates.size(); index++){ 

      State s = allStates.get(index); 

      if (s.isInitial==true) { 

       break cycle; 



      } 
     } return index; 

} 



    public void processString (String string) 
    { 


     StringBuilder stepString= new StringBuilder (string); 


     int actualStateIntIndex; 



     System.out.println("THE FOUND INITIAL ONE IS "+ theInitialStateIntIndex); 


     State firstState = allStates.get(theInitialStateIntIndex); 

     State actualState = firstState; 

     while (stepString.length()>0){ 

      Character characterToProcess = stepString.charAt(0); 
      stepString.deleteCharAt(0); 

      State nextState; 
      nextState = ((State)actualState.get(characterToProcess)); // pasa al siguiente State 

      actualState = nextState; 

      actualStateIntIndex=allStates.indexOf(actualState); 


      System.out.println("the actual state for " + stepString + " is " + actualStateIntIndex); 

      if ((actualState.isFinal==true) && (stepString.length()==0)) 
       { 
        System.out.println("THE STRING " + string + " IS ACCEPTED AT STATE " + actualStateIntIndex); 

       } 

      else if (stepString.length()==0 && (actualState.isFinal==false)){ 
        System.out.println("THE STRING " + string + " IS REJECTED AT STATE " + actualStateIntIndex); 

       } 

      } 



     } 




    } 

Answer 1

Je dirais que la représentation la plus naturelle est de modéliser chaque Etat comme Map avec des symboles de l'alphabet comme clés et états résultants (à savoir Map instances) en tant que valeurs. Une classe pour représenter un automate aurait une référence pour l'état initial, une pour l'état actuel, un Set des états et un Set des états finaux. Oh, et un Set pour l'alphabet.

Ce qui précède devrait vous donner de bonnes performances pour toutes les opérations pertinentes. Ajouter quelques méthodes pour la commodité et l'encapsulation et vous avez terminé.

Edit:

Vous avez besoin d'une State classe pour être en mesure d'utiliser les génériques correctement:

public class State extends HashMap<Character, State>{ } 

public class Automaton{ 
    private Set<State> allStates; 
    private Set<State> finalStates; 
    private State initialState; 
    private State currentState; 
    private Set<Character> alphabet; 

    public boolean doTransition(Character input)){ 
     if(!alphabet.contains(input){ 
      throw new IllegalArgumentException(); 
     } 
     if(finalStates.contains(currentState)){ 
      throw new IllegalStateException(); 
     } 

     currentState = currentState.get(input); 

     if(currentState == null){ 
      throw new IllegalStateException(); 
     } 

     return finalStates.contains(currentState); 
    } 

    // more methods go here 
} 

Pour l'automate 3 de l'État que vous avez utilisé comme exemple:

State s0 = new State(); 
State s1 = new State(); 
State s2 = new State(); 
s0.put('a', s1); 
s0.put('b', s0); 
s1.put('a', s2); 
s1.put('b', s0); 
s2.put('a', s2); 
s2.put('b', s0); 

Cette devrait se produire par des méthodes d'initialisation de la classe Automaton, bien sûr.

Answer 2

C'est un projet amusant.

Vous pourriez d'abord penser à l'interface autour de votre FSM. Comment le programmez-vous? Comment le nourrissez-vous?

Quelque chose comme:

fsm.setStates("ab"); 
fsm.setInitialState(0); 
fsm.addTransition(1,0); 
fsm.addTransition(2,0); 
fsm.addTransition(2,0); 
fsm.setFinalState... 

Si vous avez quelque chose de simple comme ça, ça va séparer votre code et à le rendre beaucoup plus facile pour vous de penser à une seule section à la fois (votre « interface utilisateur » section, qui analyse l'entrée et la passe au FSM, devrait devenir triviale) Cela laisse juste la question que vous avez effectivement demandé: comment implémenter le FSM.

Il y a probablement un million de façons, mais je pense que le plus facile à référencer et à utiliser doit être un int [] []; la syntaxe de transition sera claire et directe comme:

newState=table[oldState][transition]; 

une fois que vous avez rempli le tableau. Mais n'oubliez pas de séparer votre code et pensez à la façon dont vous voulez accéder aux classes, et pas seulement à l'étape suivante du code.