¿Puedo implementar Transiciones de estado para un DFA en Java usando java.util.Set

Question

Estoy implementando un DFA lo más cerca posible de la definición formal como ejercicio de aprendizaje (y material de blog)

Planeaba usar un java.util.Set donde un conjunto está involucrado en la definición.

La definición implica un conjunto de tuplas para definir las transiciones de estado legales: (estado, símbolo) - > nextState.

Tengo una clase de transición con miembros estado, símbolo y nextState. He implementado equals () y hashCode () para indicar que dos transiciones son iguales si coinciden en estado y símbolo. Entonces tengo un java.util.Set de Transición instancias.

En mi algoritmo de procesamiento, tengo el estado actual cuando leo el siguiente símbolo. Anticipé construir un objeto de Transición usando estos dos para extraer la Transición correspondiente del Conjunto, que luego me diría el siguiente estado, y puedo iterar.

Pero, no veo ninguna forma de extraer un miembro de un java.util.Set para su uso posterior. Puedo eliminar (Object o), pero eso solo devuelve boolean.

¿Qué estoy haciendo mal?

Answer 1

Set probablemente no sea lo que quieres usar para esto. Mi recomendación sería usar una Lista & Lt; Transition & Gt ;, o posiblemente un Map & Lt; Estado, Lista & Lt; Transición & Gt; & Gt ;. No estoy seguro de qué sería mejor sin construirlo y hacer algunos benchmarking.

Answer 2

Parece que su anulación de equals () y hashCode () es dudosa, porque la transición original coincide con la del conjunto de acuerdo con equals () y, sin embargo, los dos no son intercambiables (de lo contrario, solo usaría el nuevo transición en lugar del original.)

Probablemente desee una clase que sea solo una combinación de estado y símbolo sin otros atributos, y úsela como una clave en un Mapa. Alternativamente, podría usar un Map<State, Map<Symbol, State>>

Answer 3

Estoy de acuerdo con Matthew Brubaker en que Set probablemente no sea lo que necesita. Es posible que desee probar enums en su lugar; consulte el Glosario de Java para ver un ejemplo.

Answer 4

¿No puede lograr esto sin tener una colección externa de estados, o incluso los objetos de Transición? Si la clase de estado se define como:

public class State
{
    private Map<Symbol, State> transitions = new HashMap<Symbol, State>();

    public State() { /* populate transitions somehow */ }

    public State nextState(Symbol symbol) { return transitions.get(symbol); }
}

Luego, si tiene una referencia al estado inicial, simplemente puede moverse de un estado a otro de esta manera:

State initial = getInitialStateSomehow();
State second = initial.nextState(SYMBOL_1);
State third = initial.nextState(SYMBOL_2);  // etc...

Answer 5

Sí, estoy un poco confundido acerca de por qué incluso necesitaría una colección.

Para una máquina de estado simple, puede usar enteros estáticos y una declaración de caso para hacer su máquina de estado de esta manera:

int STATE1 = 1; 
int STATE2 = 2;
int STATE3 = 3;
int STATE4 = 4;

int currentstate = STATE1 ;
int input = nextInput();


while(currentstate != STATE4 ){
   switch(input){
      case STATE1: 
          if(input == 'a') currentstate = STATE2; 
          break;
      case STATE2: 
          if(input == 'b') currentstate = STATE3;
          else currentstate = STATE1;
          break;
      case STATE3: 
          if(input == 'c')  currentstate = STATE4;
          else currentstate = STATE1;
      }
 }

Esa es una máquina de estado básica que buscará cualquier cadena que contenga 'abc'. Podrías extender fácilmente eso también busca ab * c o lo que quieras.

¿Y qué si quieres una máquina de estado dinámica, construida en tiempo de ejecución? Bueno, yo también he hecho esto. No es muy dificil. Lo que hice fue crear una clase de estado con una lista de transiciones. Cada transición tiene un puntero al siguiente estado y los criterios para vincular.

Entonces, por ejemplo, STATE1 tendría una transición con los criterios 'a' y un puntero a algún objeto que representa STATE2. El código buscaría verificar los criterios (que podrían ser un objeto que toma un int como parámetro y devuelve verdadero o falso si coincide) y si los criterios coinciden, movería el puntero de estado al estado señalado también por la transición.

El código podría parecerse a esto

public void move(int input){
   for(transition t : currentState.transitions){
      if(t.getCriteria().matches(input)){
         currentState = t.getNextState();
         break;
      }
   }
}

Answer 6

Si solo desea implementar un motor de coincidencia de patrones, un patrón de diseño de estado puede ser innecesario ya que es poco probable que el patrón cambie. Como ha señalado Chad, usar un switch para codificar la función de transición es completamente aceptable en tales casos.

Aquí hay un ejemplo de un autómata de coincidencia de patrones no determinista que usa conjuntos:

public boolean validate() {
    Set<Integer> currentStates = new HashSet<Integer>();
    final Set<Integer> acceptingStates = new HashSet<Integer>();

    currentStates.add(0); // Initial state.
    acceptingStates.add(1);
    acceptingStates.add(3);
    acceptingStates.add(6);

    for (int i = 0; i < getInput().length(); i++) {
        char c = getInput().charAt(i);
        Set<Integer> newStates = new HashSet<Integer>();

        for (int state : currentStates) {
            switch (state) {
                case 0:
                    if (c == 'a')
                        newStates.add(1);
                    break;
                case 1:
                    if (c == 'b') {
                        newStates.add(2);
                        newStates.add(4);
                    }
                    break;
                case 2:
                    if (c == 'b')
                        newStates.add(3);
                    break;
                case 3:
                    if (c == 'b')
                        newStates.add(2);
                    break;
                case 4:
                    if (c == 'b')
                        newStates.add(5);
                    break;
                case 5:
                    if (c == 'b')
                        newStates.add(6);
                    break;
                case 6:
                    if (c == 'b')
                        newStates.add(4);
                    break;
            }
        }

        if (newStates.size() == 0)
            return false;
        currentStates = newStates;

        System.out.printf("Character read: %c\n", c);
        System.out.printf("Current states: ");
        printStates(currentStates);
    }

    for (int state : acceptingStates)
        if (currentStates.contains(state))
            return true;
    return false;
}

Este autómata reconoce palabras de entrada del lenguaje regular descrito por el patrón " a (bb * | bbb *) " ;, es decir, un & # 8220; a & # 8221; seguido de un múltiplo de dos o un múltiplo de tres muchos & # 8220; b & # 8221; s.