英文:
Is there any way to represent a DFA (Deterministic finite automata) into an adjacency List?
问题
So, I have a very big DFA and it's filled with PHI's, so I want to convert it to an adjacency list to save a lot of memory and use it to check if the input is accepted or return the state that the input stands on.
And I searched a lot about but found nothing...
I know the code for weight graphs, but in DFA machine there are multiple weights.
Another thing, when we move on a DFA transition table we use this code
state = DFA_TransitionTable[state][weight];
And I need an alternative for that.
英文:
So, I have a very big DFA and it's filled with PHI's, so I want to convert it to an adjacency list to save a lot of memory and use it to check the if input is accepted or return the state that the input stands on.
And I searched a lot about but found nothing...
I know the code for weight graphs, but in DFA machine there are multiple weights.
Another thing, when we move on a DFA transition table we use this code
state = DFA_TransitionTable[state][weight];
And I need an alternative for that.
答案1
得分: 2
这是用Java中的邻接列表表示DFA的一种方法。与其使用数组表示转移函数,你可以将其表示为一个从“符号”到“状态”的映射,这样给定一个状态和一个符号,你可以使用 state.transitionFunction.get(symbol)
来获取下一个状态。
class DFA {
Set<State> states;
State initialState;
Set<State> acceptStates;
}
class State {
Map<Symbol, State> transitionFunction;
}
class Symbol {}
这假设你想要拥有自己的 Symbol
类 - 当然,你也可以在传统用例中将DFA应用于字符串时使用字符或字符串。
英文:
Here is one way to represent a DFA with an adjacency list in Java. Instead of having an array for the transition function, you represent it as a map of "symbols" to "states", so that given a state and a symbol, you get the next state with state.transitionFunction.get(symbol)
.
class DFA {
Set<State> states;
State initialState;
Set<State> acceptStates;
}
class State {
Map<Symbol, State> transitionFunction;
}
class Symbol {}
This assumes that you want to have a Symbol
class of your own - you can of course use Character or String for the traditional use case where the DFA is applied to strings.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论