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>