module Regex. kind regex (type -> type). type emp (regex A). type eps (regex A). type chr (A -> regex A). type alt (regex A -> regex A -> regex A). type cat (regex A -> regex A -> regex A). type kle (regex A -> regex A). type match (regex A -> list A -> o). type append (list A -> list A -> list A -> o). append [] L L. append (X :: J) K (X :: L) :- append J K L. match eps []. match (chr X) (X :: []). match (alt E1 E2) L :- match E1 L. match (alt E1 E2) L :- match E2 L. match (cat E1 E2) L :- append J K L, match E1 J, match E2 K. match (kle E) []. match (kle E) L :- append J K L, match E J, match (kle E) K.

이게 코드



결과는...

(0|(1(01*0)*1))* denotes the set of binary numbers that are multiples of 3: { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ... }

라고 하니 이걸 한번 넣어보자.


[Regex] ?- match (kle (alt (cat (chr 1) (cat (kle (cat (chr 0) (cat (kle (chr 1)) (chr 0)))) (chr 1))) (chr 0))) X. The answer substitution: X = nil More solutions (y/n)? y The answer substitution: X = 0 :: nil More solutions (y/n)? y The answer substitution: X = 0 :: 0 :: nil More solutions (y/n)? y The answer substitution: X = 0 :: 0 :: 0 :: nil More solutions (y/n)? y The answer substitution: X = 0 :: 0 :: 0 :: 0 :: nil More solutions (y/n)? y The answer substitution: X = 0 :: 0 :: 0 :: 0 :: 0 :: nil

[Regex] ?- match (kle (alt (cat (chr 1) (cat (kle (cat (chr 0) (cat (kle (chr 1)) (chr 0)))) (chr 1))) (chr 0))) [0,1,1,0]. yes


되긴 되는데 teyjus 탐색 알고리즘이 DFS라 별로 흥미로운 결과는 안보여준다 ㅋㅋ

BFS 지원하는 논리형 언어 쓰면 잘 나오지 않을까 싶은데.



+ DFA 안쓰고 걍 regex 다뤄서 별로 어렵지 않게 풀 수 있을듯