有没有办法将确定性有限自动机(DFA)表示为邻接列表?

huangapple go评论110阅读模式
英文:

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&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.

huangapple
  • 本文由 发表于 2020年8月1日 16:09:49
  • 转载请务必保留本文链接:https://go.coder-hub.com/63203123.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定