如何确定有限状态自动机是否具有确定性？

Question

如何编写Java代码来确定给定的自动机是否具有确定性。我有一个代表自动机的类，它有以下五个变量：

java prettyprint-override">int alphabet_size;
int n_states;
int delta[][];
int initial_state;
int accepting_states[];

Δ表示如下所示，例如，在实际自动机中，程序中的q1,1，q2看起来像{1,1,2}。我知道在一个非确定性自动机中，可能有多个可能的状态，但我不知道如何计算。

Answer 1

对于您现在拥有的成员变量，您只能表示确定性的FSA。为什么？因为NDFSA是一个状态q₁和输入a的状态

• （q₁，a）-

在delta中。您实现这个（q_from，输入）-

一个非常快速的解决方案是允许所有instate输入对都有一个Outstate列表，如下所示：

ArrayList[][] delta;

然而，这是丑陋的。如果你意识到delta实际上是来自-

• （q_from-

另一件需要认识的事情是，int[]在概念上与Map相同

Map<Integer, Map<Integer, List<Integer>>> delta;

无论您选择哪种实现，决定FSA是否具有确定性的测试都非常简单，并且来自定义：A是DFSA，如果delta中所有列表的长度是

*请注意，真正的FSA库通常使用不同的方法。例如，foma使用一个过渡对象数组，其中包含instate、outstate和输入字符字段。然而，对于初学者来说，上面这些可能更容易处理。

Answer 2

为了解决这个问题，我会这样做：

1. 创建一个映射（String、String或integer），我将使用键检查实际状态

如果你能遍历整个数组，它就是确定性的！