module NFA where
-- SPDX-FileCopyrightText: Chris Pressey, the original author of this work, has dedicated it to the public domain.
-- For more information, please refer to <https://unlicense.org/>
-- SPDX-License-Identifier: Unlicense
type State = Integer
data (Eq a) => Transition a = Transition State a State
moveOnce :: (Eq a) => [Transition a] -> [State] -> a -> [State]
moveOnce nfa states input =
[there | (Transition here x there) <- nfa, x == input, here `elem` states]
moveMany :: (Eq a) => [Transition a] -> [State] -> [a] -> [State]
moveMany nfa = foldl (moveOnce nfa)
--
-- Accepts (in state 6) the strings "ask" and "apt",
-- but not "ast" or "apk"
--
egNFA :: [Transition Char]
egNFA = [
Transition 1 'a' 2,
Transition 1 'a' 4,
Transition 2 's' 3,
Transition 3 'k' 6,
Transition 4 'p' 5,
Transition 5 't' 6
]
test str = moveMany egNFA [1] str