# 有没有办法将确定性有限自动机（DFA）表示为邻接列表？

go评论103阅读模式

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

``````class DFA {
Set<State> states;
State initialState;
Set<State> acceptStates;
}

class State {
Map<Symbol, State> transitionFunction;
}

class Symbol {}
``````

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&lt;State&gt; states;
State initialState;
Set&lt;State&gt; acceptStates;
}

class State {
Map&lt;Symbol, State&gt; 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.

• 本文由 发表于 2020年8月1日 16:09:49
• 转载请务必保留本文链接：https://go.coder-hub.com/63203123.html
• c#
• dfa
• graph
• java
• state

go 63

go 50

go 50

go 61