在 Haskell 中表示有限自动机的好方法是什么？它的数据类型是什么样的？
在我们学院，自动机被定义为 5 元组
(Q, X, delta, q_0, F)
其中 Q 是自动机状态的集合，X 是字母表（这部分是否必要），delta 是从 (Q,X) 获取 2 元组并返回状态/-s 的转换函数（在非确定性版本中）， F 是接受/结束状态的集合。
最重要的是，我不知道什么类型delta应该有...
有两个基本选项：
- 显式函数
delta :: Q -> X -> Q (or [Q]正如斯文·海格所建议的那样。
- A map
delta :: Map (Q, X) Q例如使用Data.Map，或者如果您的州/字母表可以按升序数字索引Data.Array or Data.Vector.
请注意，这两种方法本质上是等效的，可以从映射版本转换为函数版本（由于额外的原因，这略有不同）Maybe来自lookup调用）相对容易
delta_func q x = Data.Map.lookup (q,x) delta_map
（或者针对您使用的任何映射类型的查找函数的适当柯里化版本。）
如果您在编译时构造自动机（因此知道可能的状态并可以将它们编码为数据类型），那么使用函数版本可以为您提供更好的类型安全性，因为编译器可以验证您是否已涵盖所有情况。
如果您在运行时构建自动机（例如，根据用户输入），则存储delta作为映射（并且可能执行上面的函数转换）并具有适当的输入验证来保证正确性，以便fromJust是安全的（即地图中总是有一个条目用于任何可能的(Q,X)元组，因此查找永远不会失败（永远不会返回Nothing)).
非确定性自动机与映射选项配合得很好，因为查找失败与没有状态可去相同，即空的[Q]列表，所以不需要any的特殊处理Maybe除了打电话给join . maybeToList (join来自Data.Monad and maybeToList来自Data.Maybe).
另一方面，字母表绝对是必要的：它是自动机接收输入的方式。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
