完成haskell命令的正确路径指南

Question

我是哈斯克尔的新人.我的java知道如何帮助我很多.

我需要任何帮助或指导来完成代码.我已经尝试了大部分部分,并对我倾向于实现的目标发表评论.

DFA定义如下(DFA定义的原始图像):

Q = {q1,q2,q3,q4,q5}
qs = q1
F = {q4}
delta = {
  <q1,0,q2>,<q1,1,q2>,<q1,.,q3>,
  <q2,0,q2>,<q2,1,q2>,<q2,.,q4>,
  <q3,0,q4>,<q3,1,q4>,<q3,.,q5>,
  <q4,0,q4>,<q4,1,q4>,<q4,.,q5>,
  <q5,0,q5>,<q5,1,q5>,<q5,.,q5>
  }
Sigma = {0,1,.}

任务:

1. 创建一个Haskell语言程序,可用于执行任何与上述FDA定义相对应的任意确定性有限自动机.将DFA表示为四元组

   一个.表示每个状态,其名称为String

   湾 将所有州表示为州列表

   C.将每个转换表示为三元组,将转换列表表示为列表.

2. 为了帮助您,请在解决方案中实施以下功能:

   一个.stateFactory - 返回DFA定义(即四元组)

   湾 allStates,firstState,finalStates和allTransitions - 获取DFA并返回DFA的相应组件.例如,在上面的DFA实例中,allStates将返回状态列表q 1,q 2,q 3,q 4和q 5.

   C.transFrom,transInput和transTo - 进行转换并返回转换的相应组件

   d.findTransition - 获取状态,标签和转换列表,并返回包含与给定状态和字符匹配的单个转换的列表(请注意,从状态发出的转换由每个字符标签唯一确定

   即 findNextState - 获取DFA,标签和状态并返回状态

   F.dfaAccept - 接受DFA和输入String,如果DFA接受输入则返回True,否则返回False(即,一次分解字符串一个字符,因为您的解决方案必须适用于任何DFA,所以不匹配整个字符串).将其分成两个函数是有帮助的,每个函数具有不同的参数集(一个用于空列表,一个用于非空列表).一个函数采用当前状态,一个函数只采用DFA,其状态被假定为DFA的初始状态.

这是我的代码有很多错误,但我正在尝试修复它们

allStates = ["q1","q2","q3","q4","q5"] -- iniitialize all states
firstState = "q1"
finalStates = "q4"

--define all transitions as a tuple

t1 = ("q1",'0',"q2")
t2 = ("q1",'1',"q2")
t3 = ("q1",'.',"q3")

-- place all transitions in a list
allTransitions = [t1,t2,t3]

lst =[]

stateFactory = (allStates, firstState, finalStates, allTransitions)

findTransition state label listOfTransition = 
    if (state , label , "q1") elem listOfTransition
        then lst ++ [] -- if the tuple matches the one in transition add to list
    else
        lst -- no match dont add

    if (state , label , "q2") elem listOfTransition
        then lst ++ [] -- if the tuple matches the one in transition add to list
    else
        lst -- no match dont add

    if (state , label , "q3") elem listOfTransition
        then lst ++ [] -- if the tuple matches the one in transition add to list
    else
        lst -- no match dont add

findNextState DFA label state = 
    --get the transition and extract the last element which is the state
    last findTransition state label allTransitions

dfaAccept DFA inputString = 
    if inputString == null then False

预期产出

Prelude> dfaAccept stateFactory “”
False
Prelude> dfaAccept stateFactory “1”
False
Prelude> dfaAccept stateFactory “1.0”
True
Prelude> dfaAccept stateFactory “11.11”
True
Prelude> dfaAccept stateFactory “10.10.10”
False

Answer 1

这是你正在上课的作业,还是这个自我引导的Haskell研究？如果这是自我引导的话,我想你可能会在这个阶段尝试一项对你来说太难的练习.我建议你看一下这个答案: Haskell入门.即使这是一个古老的答案,它已经不断更新,并且大部分资源仍然有用.该http://www.haskell.org网站上也有链接,大量的资源用于学习Haskell,"文档"部分.

如果这是你正在上课的作业,你可能会遇到麻烦.你在代码中犯了一些非常基本的错误(使用elem你需要的地方`elem`;尝试应用last四个参数;使用大写标识符DFA作为变量名),这表明你还没有确定Haskell的基本原理.

也许你应该和你的教授谈谈,让他或她知道这个任务超出你的范围.也许你可以得到一个扩展,或者你可以提供一个Java解决方案来获得部分功劳(假设这门课程不是特别是Haskell课程).

如果你坚持前进,这里有一个暗示.您正在寻求帮助编写最难的功能之一,findTransition但您甚至没有编写"简单"的功能,例如allStates,firstState等等.(您在解决方案中使用了相同的名称,但是您已将它们定义为特定DFA的常量,而不是将它们应用于常规DFA元组,这是分配所需的).

那么,您是否可以通过填写下划线来完成以下模板,以回答第1部分和第2部分(b)？

-- simple type synonyms to make things easier to read
type State = String
type Symbol = Char

-- some more complicated type synonyms
type Transition = (State, Symbol, State)
type DFA = ( [State]        -- all states
           , State          -- first state
           , [State]        -- final states
           , [Transition]   -- all transitions
           )

allStates :: DFA -> [State]
allStates _ = _

firstState :: DFA -> State
firstState _ = _

finalStates :: DFA -> [State]
finalStates _ = _

allTransitions :: DFA -> [Transition]
allTransitions _ = _

一旦你能够做到这一点,写下第2(c)部分中的函数.一旦你完成了所有这些,你可能已经准备好解决了findTransition.此时,您可能需要了解这些find或filter函数,否则您将需要学习如何编写递归列表函数.