Haskell 可以处理任意确定性有限自动机的程序

Question

={0,1,2,3,4}
=0 
={3} 
=〈0,0,1〉,〈0,1,1〉,〈0,.,2〉,〈1,0,1〉,〈1,1,1〉,
〈1,.,3〉,〈2,0,3〉,〈2,1,3〉,〈2,.,4〉,〈3,0,3〉,〈3,1,3〉,
〈3,.,4〉〈4,0,4〉,〈4,1,4〉,〈4,.,4〉}

Where Σ={0,1,.}.

我正在开发一个 Haskell 程序，它可以处理基于上述定义的任意确定性有限自动机。我应该将每个状态的名称表示为字符串，将所有状态表示为状态列表，将每个转换表示为三元组，并将转换列表表示为列表。

我已经修改了我的代码并且它可以运行，但我可以说我没有按照要求走在正确的轨道上。我是 Haskell 的新手，非常感谢您提供有关如何使我的代码更好的指导，或者如果我完全偏离了它的方向。我真的很想了解这一切是如何运作的；我已经阅读了许多不同的示例和教程，但我只是在特别努力地编写代码。

编辑：具体来说，当我输入下面给出的示例时，除了 dfaAccept dfaFactory "10.11" 之外，我得到了正确的输出。这返回为 false 而不是 true，并且 dfaAccept dfaFactory "" 结果为 true 而不是 false。我没有看到导致此问题的错误所在。此外，我想确保我的代码在可读性方面有意义。

type State = Int
type DFA = ([State], [Char], State->Char->State, State, [State])

dfaFactory :: DFA
dfaFactory = (states, alphabet, delta, s, fs)
    where states = [1,2,3]
    alphabet= ['1','0','.']
    s = 1
    fs = [1]
    delta 1 '1' = 2
    delta 1 '0' = 2
    delta 1 '.' = 2                        
    delta 2 '1' = 3
    delta 2 '0' = 3
    delta 2 '.' = 3
    delta 3 '1' = 1
    delta 3 '0' = 1
    delta 3 '.' = 1

extendDelta :: (State -> Char -> State) -> (State -> String -> State)
extendDelta delta = deltaStar
  where deltaStar q [] = q
  deltaStar q (a:w) = deltaStar (delta q a) w                        

dfaAccept :: DFA -> String -> Bool
dfaAccept (qs,alpha,delta,s,fs) w =
  let deltaStar = extendDelta delta
  q = deltaStar s w
  in elem q fs

示例输出如下所示：

Prelude> dfaAccept dfaFactory “”
False
Prelude> dfaAccept dfaFactory “1”
False
Prelude> dfaAccept dfaFactory “1.0”
True
Prelude> dfaAccept dfaFactory “10.11”
True
Prelude> dfaAccept dfaFactory “10.10.10”
False

编辑我正在努力实现这些最终要求...只是不确定如何实现。一个。将每个状态的名称表示为字符串 b.将所有状态表示为状态列表 C。将每个转换表示为三元组，将转换列表表示为列表。一个。 dfaFactory – returns 一个“硬编码”DFA 定义（即一个四元组）b。 getStates、getFirstState、getFinalStates 和 getTransitions – 采用单个 DFA 参数和 return DFA 的相应组件。 C。 getFromState、getLabel 和 getToState – 采用单个转换参数和 return 相应的转换组件 d. matchTransition – 采用状态、输入字符和转换，如果给定状态和输入与给定转换的起始状态和标签匹配，则 returns 为真 e. findNextState – 接受一个 DFA、一个输入字符和一个当前状态，并 returns 基于此输入和状态的 DFA 中的状态。 F。 dfaAccept – 采用 DFA 和输入字符串，如果 DFA 接受输入则 returns 为 True，否则为 False。使用它来调用 dfaAccept1 辅助函数 G。 dfaAccept1——接受一个输入字符串、一个当前状态和一个 DFA。一次分解输入字符串一个字符，不要匹配整个字符串，因为您的解决方案必须适用于任何 DFA）。这是一个具有基本和递归情况的递归函数。

Answer 1

您的方向是正确的，因为您的 DFA 结构是正确的，但是您没有实现给定的所有规范：

首先，您的 DFA 应该有 5 个状态：states = [0,1,2,3,4]

字母表是对的，起始状态也是对的。但是在你的规范中你可以看到 accepting state 是 3，所以你需要把它放在你的代码中：fs = [3]

最后你的 delta 函数是错误的。它们应该是这样的：

delta 0 '0' = 1
delta 0 '1' = 1
delta 0 '.' = 2
delta 1 '0' = 1
delta 1 '1' = 1
delta 1 '.' = 3
delta 2 '0' = 3
delta 2 '1' = 3
delta 2 '.' = 4
delta 3 '0' = 3
delta 3 '1' = 3
delta 3 '.' = 4
delta 4 '0' = 4
delta 4 '1' = 4
delta 4 '.' = 4

此外，您可以看到您的增量可以轻松简化：在任何状态下输入 0 或 1 都是相同的，因此您可以使用更简单的模式匹配来获得它。此外，4 是一个黑洞状态，即它总是映射到自身。因此，您可以将增量重写为：

delta 4  _  = 4
delta 0 '.' = 2
delta 0  _  = 1
delta 1 '.' = 3
delta 1  _  = 1
delta 2 '.' = 4
delta 2  _  = 3
delta 3 '.' = 4
delta 3  _  = 3

此外，正如其他人在评论中指出的那样，您的 extendDelta 和 deltaStar 只是应用左折叠的一种奇怪方式。 fold' 通常更好，因为它不会建立堆栈，所以我将使用它。您需要从 Data.List

导入它

所以这是你的最终 DFA：

import import Data.List
type State = Int
type DFA = ([State], [Char], State->Char->State, State, [State])


dfaFactory :: DFA
dfaFactory = (states, alphabet, delta, s, fs)
              where
                states = [0,1,2,3,4]
                alphabet= ['1','0','.']
                s = 0
                fs = [3]
                delta 4  _  = 4
                delta 0 '.' = 2
                delta 0  _  = 1
                delta 1 '.' = 3
                delta 1  _  = 1
                delta 2 '.' = 4
                delta 2  _  = 3
                delta 3 '.' = 4
                delta 3  _  = 3

dfaAccept :: DFA -> String -> Bool
dfaAccept (qs,alpha,delta,s,fs) w = finalState `elem` fs
                                      where
                                        finalState = foldl' delta s w

Haskell 可以处理任意确定性有限自动机的程序

Haskell program that can handle any arbitrary deterministic finite automaton

haskell

dfa