Posso implementar transições de estado para uma DFA em Java usando java.util.Set
-
22-07-2019 - |
Pergunta
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?
Solução
Set provavelmente não é o que você deseja usar para isso. Minha recomendação seria usar um List
Outras dicas
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>>
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.
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...
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;
}
}
}
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.