1

我必须在 Java 中通过自动机实现以下操作：

  • 级联
  • 克莱恩之星
  • 联盟
  • 路口

如果自动机是 NFA，那么这些操作会更容易。我喜欢以下链接Modeling a Finite Deterministic Automaton via this data中给出的实现，但我认为这在建模 NFA 时不太合适，因为关键唯一性限制。你会给我推荐任何对 NFA 建模的解决方法吗？

4

2 回答 2

2

As someone who actually implemented these operations once (when building a scanner generator), I recommend building up the automaton as an NFA, then using an algorithm like the subset construction or Thompson's algorithm to convert it down to a DFA. This keeps the logic for combining automata together simple and elegant without sacrificing the speed of the resulting matching automaton.

Hope this helps!

于 2012-06-05T15:26:27.590 回答
0

我建议使用 DFA。尽管在纸面上形成 NFA 可能更容易，但由于考虑到 epsilon-jump，检查一个有效字符串与一个 NFA 将比验证一个 DFA 更复杂。

至于对它们建模，您应该能够只用几个类编写自己的。想想 DFA/NFA 由什么组成：
- 开始状态
- 状态集（其中一些是“接受”状态）
- 转换集

于 2012-06-05T15:08:20.543 回答