Posso implementar transições de estado para uma DFA em Java usando java.util.Set

Question

Estou implementando um DFA tão perto quanto eu posso para a definição formal como um exercício de aprendizagem (e blogs de material)

Eu planejava usar um java.util.Set onde um conjunto está envolvido na definição.

A definição envolve um conjunto de tuplas para definir os legais transições de estado:. (Estado, símbolo) -> nextState

Eu tenho uma classe de transição com o estado membros, símbolo e nextState. Eu tenho implementado equals () e hashCode () para indicar que dois Transitions são iguais se eles correspondem no estado e símbolo. Em seguida, tenho um java.util.Set de Transição casos.

Na minha algoritmo de processamento, tenho o estado atual quando li o próximo símbolo. Eu previa a construção de um objeto de transição usando os dois para tirar a transição correspondente do Set, o que então me diga o próximo estado, e eu pode iterar.

Mas - Eu não vejo nenhuma maneira de extrair um membro de uma java.util.Set para uso posterior. I pode remover (Object o), mas que apenas o retorno boolean.

O que estou fazendo de errado?

Answer 1

Set provavelmente não é o que você deseja usar para isso. Minha recomendação seria usar um List , ou possivelmente um Map >. Eu não tenho certeza que seria melhor sem realmente construí-lo e fazer algumas benchmarking.

Answer 2

Parece como se sua substituir de equals () e hashCode () é duvidosa, porque a transição originais corresponde a um no conjunto de acordo com equals () e ainda os dois não são intercambiáveis ??(caso contrário você iria usar apenas o novo transição no lugar do original.)

Você provavelmente vai querer uma classe que é apenas uma combinação de estado e símbolo sem outros atributos, e usar isso como uma chave em um mapa. Alternativamente, você pode usar um Map<State, Map<Symbol, State>>

Answer 3

Eu concordo com Matthew Brubaker que Set provavelmente não é o que você precisa. Você pode querer tentar enums vez; veja a Java Glossário para um exemplo.

Answer 4

Você não pode fazer isso sem ter algum coleta externa dos estados, ou até mesmo os objetos transição? Se a classe Estado é definido 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); }
}

Então, se você tem uma referência para o estado inicial, você pode simplesmente mudar de estado para estado como esta:

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

Answer 5

Sim, eu sou uma espécie de confuso sobre por que ainda precisa de uma coleção em tudo.

Para uma máquina de estado simples que você pode usar apenas números inteiros estáticos e uma instrução case para fazer sua máquina de estado como esta:

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;
      }
 }

Isso é uma máquina estatal básica que vai olhar para qualquer string contendo 'abc'. Você poderia facilmente estender isso também procurar ab * c ou o que quiser.

Assim que se você quer uma máquina de estado dinâmico, construído em tempo de execução? Bem, eu fiz isso também. Não é muito difícil. O que eu fiz é criar uma classe Estado com uma lista de transições. Cada transição possui um ponteiro para o próximo estado, e os critérios para link.

Assim, por exemplo, estado1 teria uma transição com os critérios de 'a' e um ponteiro para um objeto que representa State2. O código ficaria verificar os critérios (que poderia ser um objeto que leva um int como um parâmetro e retorna verdadeiro ou falso se ele corresponde) e se os critérios combinados, seria mover o ponteiro para o estado apontado também pela transição.

O código poderia ser algo como ths

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

Answer 6

Se você quiser apenas para implementar um mecanismo de correspondência de padrão, um projeto Estado Padrão poderia ser desnecessário, já que o tamborilar é improvável que a mudança. Como Chad tem as pontas, usando um switch para codificar a função de transição é completamente aceitável em tais casos.

Aqui está um exemplo de um padrão de autômato correspondência nondeterministic 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ômato reconhece palavras de entrada da linguagem regular descrito pelo "a(bb*|bbb*) padrão", ou seja, um‘a’seguido por um múltiplo de dois ou um múltiplo de três muitos‘b’s.