Применение переходов PDA к списку входных строк в haskell

Question

Я пытаюсь внедрить 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,