Я пытаюсь внедрить PDA в Haskell на основе заметок моего лектора, она описала нам общий процесс и оставила фактическую реализацию функции до нас.Я чувствую, что у меня большая часть этого работает, одна маленькая ошибка в функции nextsteps.
Правила КПК следующие:
[((1,"a",""),(1,"a")),((1,"b",""),(1,"b")),((1,"a",""),(2,"")),((1,"b",""),(2,"")),((1,"",""),(2,"")),((2,"a","a"),(2,"")),((2,"b","b"),(2,""))]
run :: PDA -> String -> Result
run _ "" = Reject
run (state,finalState,rules) str = findpath [(state,str,""(state,finalState,rules)
data Result = Accept | Reject deriving Show
type PDA = (Int,[Int],[Transition])
-- Takes in the start state, the current value read by the input string, the current stack and the new state along with the change to the stack
-- ((1,"a",""),(1,"a"))
type Transition = ((Int, String, String),(Int,String))
-- contains the current state, current input string and current state of the stack
-- (1,"abba","ba")
type Configuration = (Int, String, String)
--if the list of configurations isnt accepted, apply the PDA transitions to it and try again
findpath :: [Configuration] -> PDA -> Result
findpath [] pda = Reject
findpath (h:t) (a,b,c) = if accept (h:t) b == True then Accept else findpath (nextsteps (h:t) c) (a,b,c)
accept' :: Configuration -> [Int] -> Bool
accept' config [] = False
accept' (x,y,z) [a] = if x == a && y == "" && z == "" then True else False
accept:: [Configuration] -> [Int] -> Bool
accept [] _ = False
accept _ [] = False
accept (h:t) finalState = if accept' h finalState then True else accept t finalState
-- apply a given transition to a configuration based on the values in the configuration and transition
step :: Configuration -> Transition -> [Configuration]
step (a,b,"")((d,"",""),(g,"")) = if a == d then [(g,b,"")] else []
step (a,(b:bs),"")((d,"",""),(g,h)) = if a == d then [(g,bs,[b])] else []
step (a,(b:bs),"") ((d,"",f),(g,"")) = if a == d then [(g,(b:bs),f)] else []
step (a,(b:bs),"") ((d,"",f),(g,h)) = if a == d then [(g,(b:bs),h)] else []
step (a,(b:bs),"") ((d,[e],""),(g,"")) = if a == d && b == e then [(g,bs,"")] else []
step (a,(b:bs),"") ((d,[e],""),(g,h)) = if a == d && b == e then [(g,bs,[b])] else []
step (a,(b:bs),"") ((d,[e],f),(g,"")) = if a == d && b == e then [(g,bs,"")] else []
step (a,(b:bs),"") ((d,[e],f),(g,h)) = if a == d && b == e then [] else []
step (a,b,c) ((d,"",""),(g,"")) = if a == d then [(g,b,c)] else []
step (a,(b:bs),c) ((d,"",""),(g,h)) = if a == d then [(g,bs,c)] else []
step (a,b,(c:cs))((d,"",[f]),(g,"")) = if a == d && c == f then [(g,b,cs)] else []
step (a,b,(c:cs)) ((d,"",[f]),(g,h)) = if a == d && c == f then [(g,b,cs++h)] else []
step (a,(b:bs),c) ((d,[e],""),(g,"")) = if a == d then [(g,bs,c)] else []
step (a,(b:bs),c) ((d,[e],""),(g,h)) = if a == d && b == e then [(g,bs,[b]++c)] else []
step (a,(b:bs),(c:cs)) ((d,[e],[f]),(g,""))= if a == d && b == e && c == f then [(g,bs,cs)] else []
step (a,(b:bs),(c:cs)) ((d,[e],[f]),(g,h)) = if a == d && b == e && c == f then [(g,bs,cs++h)] else []
-- apply the entire ruleset of the PDA over one configuration and return a list of the results
steps :: Configuration -> [Transition] -> [Configuration]
steps config [] = []
steps (a,b,c) (h:t) = if b /= "" then step (a,b,c) h ++ steps (a,b,c) t else []
-- take in a list of configurations and apply the entire rulest over each configuration and return a list of results
nextsteps :: [Configuration] -> [Transition] -> [Configuration]
nextsteps config [] = []
nextsteps (h : t) rules = steps h rules ++ nextsteps t rules
Программа работает для определенных строк, а не для других, я уверен, что это делатьс моей функцией nextsteps.В заметках моего лектора она приводит пример nextsteps [(1,"bbabba","a"),(2,"abbabba",""),(2,"bbabba","") rules = [(1,"babba","ba"),(2,"babba","a"),(2,"bbabba","a")]
Однако, когда я вызываю функцию на тех же самых входах, я получаю [(1,"babba","ba"),(2,"babba","a"),(2,"babba","a"),(2,"bbabba","a")].
Я не уверен, откуда берется это дополнительное дублирующее значение, и это основная причина, по которой строки, которые не должны быть исключены, принимаются.Я попытался удалить хвост списка конфигураций и применить только функцию шагов к заголовку списка, и это позволит убедиться, что любой список, который не должен быть принят, это Rejected, но также Rejected входные данные, которые должны бытьAccepted.