git @ Cat's Eye Technologies Dipple / master haskell / NFA.hs
master

Tree @master (Download .tar.gz)

NFA.hs @master — raw · history · blame 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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