Strong Simulation Checker

すごい適当。明日には読めないソースであることよ(詠嘆)。

trans = [("p0","a","p1"),("p1","b","p2"),("p1","c","p3")
        ,("q0","a","q1"),("q0","a","q1'"),("q1","b","q2"),("q1'","c","q3")]
simulates :: String -> String -> Bool
simulates p q =
    let t1 = [ (s,l,t) | (s,l,t) <- trans, q==s ] in
    let f (ss,ll,tt) = [ (t,tt) | (s,l,t) <- trans, s==p, ll==l ] in
    let t2 = map f t1 in
    all (any (uncurry simulates)) t2

trans で表した LTS はこんな感じ。

           p2
         b/
    a    / c
p0 --> p1 --> p3

        b
    q1 --> q2
  a/
  / a       c
q0 --> q1' --> q3

で、実行結果。

Main> "p0" `simulates` "q0"
True
Main> "q0" `simulates` "p0"
False
Main> "p1" `simulates` "q1"
True
Main>