Haskell中的有限自动机 [英] Finite automaton in Haskell

问题描述

在Haskell中表示有限自动机的好方法是什么？它的数据类型如何？

在我们学院，自动机被定义为一个5元组

 （Q，X，delta，q_0，F）
  

其中Q是自动机状态的集合，X是字母表（这部分甚至是必要的），δ是从（Q，X）和返回状态/ -s（在非确定性版本中）采用2元组的转换函数，并且F是接受/结束状态的集合。

最重要的是，我不确定什么类型的 delta 应该有...

解决方案

有两个基本选项：

• 显式函数 delta :: Q - > X - > Q （或 [Q] ），就像Sven Hager所建议的那样。
  
• 地图 delta :: Map（Q，X）Q 例如使用 Data.Map ，或者如果您的状态/字母表可以通过升序索引 Data.Array 或 Data.Vector 。

请注意，这两种方法基本上是等价的，由于 lookup 调用中的额外的 Maybe ）地图版本变为函数版本（稍有不同）

  delta_func qx = Data.Map.lookup（q，x）delta_map 
  

（或者您正在使用的任何映射类型的查找函数的适当curried版本。）

如果你在编译时构造自动机（并且知道可能的状态并且可以将它们编码为数据类型），那么使用函数版本会给你更好的类型安全性，因为编译器可以验证您是否覆盖了所有案例。

如果您在运行时（例如，来自用户输入）构造自动机，t作为一个映射存储 delta 并且可以进行适当的输入验证，以保证正确性，使得 fromJust 是安全的（即对于任何可能的（Q，X）元组，总是有一个入口，因此查找永远不会失败（永远不会返回 Nothing <



非确定性自动机可以和map选项一起工作，因为失败的查找和没有状态一样，即一个空的 [Q] 列表，所以不需要 特殊处理 Maybe 超出对连接的调用。 maybeToList （ join ）来自 Data.Monad 和 maybeToList 来自 Data.Maybe ）。

---

在另一个说明中，字母表是绝对必要的：它是自动机接收输入的方式。

What is a good way to represent finite automaton in Haskell? How would the data type of it look like?

In our college, automata were defined as a 5-tuple

(Q, X, delta, q_0, F)

where Q is the set of automaton's states, X is the alphabet (is this part even necessery), delta is the transition function taking 2-tuple from (Q,X) and returning state/-s (in non-deterministic version) and F is the set of accepting/end states.

Most importantly, I'm not sure what type delta should have...

解决方案

There are two basic options:

• An explicit function delta :: Q -> X -> Q (or [Q] as appropriate) as Sven Hager suggests.
• A map delta :: Map (Q, X) Q e.g. using Data.Map, or if your states/alphabet can be indexed by ascending numbers Data.Array or Data.Vector.

Note that these two approaches are essentially equivalent, one can convert from the map version to a function version (this is slightly different due to an extra Maybe from the lookup call) relatively easily

delta_func q x = Data.Map.lookup (q,x) delta_map

(Or the appropriately curried version of the look-up function for whatever mapping type you are using.)

---

If you are constructing the automata at compile time (and so know the possible states and can have them encoded as a data type), then using the function version gives you better type safety, as the compiler can verify that you have covered all cases.

If you are constructing the automata at run time (e.g. from user input), then storing delta as a map (and possibly doing the function conversion as above) and having an appropriate input validation that guarantees correctness so that fromJust is safe (i.e. there is always an entry in the map for any possible (Q,X) tuple and so the look-up never fails (never returns Nothing)).

Non-deterministic automata work well with the map option, because a failed look-up is the same as having no state to go to, i.e. an empty [Q] list, and so there doesn't need to be any special handling of the Maybe beyond a call to join . maybeToList (join is from Data.Monad and maybeToList is from Data.Maybe).

---

On a different note, the alphabet is most definitely necessary: it is how the automaton receives input.

这篇关于Haskell中的有限自动机的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！