java - 如何为 NFA 制作状态转换表？

Question

我已经使用二维数组为 DFA 创建了转换表。例如，存储 10 个状态和两个转换。

transition = new int[10][2]; 

但是，对于 NFA 来说，我们还有许多可能的过渡要做。下面的例子，当值 0 到来时，您可以转到 S2 或 S3。所以，我不知道应该使用哪种 Java 结构。

我正在尝试为 NFA 创建表一天，但我所做的所有方法都非常复杂。例如使用Hashtable、Set等。

您能否分享一个代码示例或任何想法？

Answer 1

为每个状态使用一个位集，并为每个转换使用按位或|。例如，S1 = 001，S2 = 010，S3 = 100。现在 S2 | S3 = 110，因此您的 {S2, S3} 转换为 110。如果用 int 表示，则最多允许 32 个状态；如果用 long 表示，则最多允许 64 个状态；对于更多状态(或更易于使用的按位运算)，请使用 BitSet .

顺便说一句，任何 NFA 都可以转换为 DFA，请参见例如http://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/nfa-2-dfa.html获取教程，因此这可能是另一种选择，具体取决于您在此处尝试执行的操作。