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的教程，这样可以是另一种选择，具体取决于您在这里尝试做什么。