木オートマトン
仕事の関係で、先輩が、木オートマトンで実現できるといわれたので、調べていたら
じつはDAGオートマトンの話であることがわかった。くやしいので、木オートマトン
の例を挙げる。
http://www.cs.cmu.edu/~neelk/や、Tree automataを参照
A tree automaton is a tuple A = (Q, F , Qf , ∆), where Q is a set of states, the final states Q f ⊆ Q, and ∆ is a relation whose elements are written like this:
f (q1, · · · , qn) → q, with n = a(f ).
というわけでこれがサンプル
Let F = {0, 1, not/1, and/2, or/2}, Q = {q0, q1}, and Qf = {q1},
and ∆ =
0 → q0, and(q0, q0) → q0, or(q0, q0) → q0
1 → q1, and(q1, q0) → q0, or(q1, q0) → q1
not(q1) → q0, and(q0, q1) → q0, or(q0, q1) → q1
not(q0) → q1, and(q1, q1) → q1, or(q1, q1) → q1Do an example evaluation of and(not(0), or(0, and(1,1)))
on the board.
答えはこうなるんじゃ
→and(not(q0),or(q0,and(q0,q0))
→and(q1,or(q0,q0))
→and(q1,q0)
→a0
