在为动态 DFA 编写代码时如何表示转换？

Question

我想编写一个 java 程序来为具有任何字母的任何语言构建一个动态有限自动机，然后测试机器接受或拒绝任何给定的单词。

我输入了状态编号、字母表、开始状态和最终状态，但在写转换时停了下来，这是有限自动机的主要内容。

Answer 1

这是一个不错的项目。正如您所说，您首先需要仔细定义一种输入语言来描述任何 FA。除了您已有的之外，您还需要状态转换。这通常通过以下两种方式之一完成：

完整过渡table。
转换图的描述，其中缺失的边被解释为到 "crash." 的转换，即到 "black hole" 状态的转换，一个具有自循环的非接受状态该语言的所有字符。

表格 1 更易于阅读，但不太方便，因为您必须明确指定所有转换。表格2更方便。我推荐表格 2。使用此表格的 DFA 描述可能如下所示：

4  # There are 4 explicit states (plus a 5th for the "black hole")
   # Assume they have state numbers 0 (the start state), 1, 2, 3.
ab # A string of characters in the FSM alphabet
1 3 # Numbers of accepting states.
5 # Number of explicit state transitions
0 1 a # From 0 to 1 on input a
1 1 a # From 1 to 1 on input a
1 2 b # From 1 to 2 on input b
2 3 a # From 2 to 3 on input a
3 3 a # From 3 to 3 on input a

您当然可以想出更奇特的语言，但这一种就足够了，而且解析起来也很简单。

请注意，具有 4 个状态和 2 个输入字符的完全指定的 DFA 具有 2(4)(4-1) = 24 个转换，而我们在此机器中只给出了其中的 5 个。要填充剩余的，请添加一个 "black hole" 状态 4。这对所有字符都有一个自循环。对于缺少某个字符 c 上的传出转换的每个节点 i，添加一个转换 i 4 c 以完成 DFA。

要在 Java 中表示 DFA，一个不错的选择是 Map<Integer, Map<Character, Integer>>。第一个映射键是州编号。第二个是输入字符。最终值是另一个状态编号。因此，如果您当前处于 s 状态并且输入字符是 c，您将获得下一个状态

nextState = transitionMap.get(s).get(c)

请注意，无需显式添加状态 4 或所有转换。相反，在评估上面的表达式时，只要 nextState 结果是 null.

就可以让机器拒绝

在为动态 DFA 编写代码时如何表示转换？

how do i represent transitions when writing a code for a dynamic DFA?

java

finite-automata

dfa

computation-theory