我想要一些例子,如何采取两个有限自动机的交集(与图表)。
我学会了取两个有限自动机的并集。
我在互联网上找遍了,但什么也没找到。
发布于 2013-11-04 21:48:04
这个想法非常简单,尽管我可以看到混淆的原因。我将通过笛卡尔乘积机器构造(与您所说的相同),对制造交集(并集,差集)机器的过程进行文本/符号描述。
DFA是一个5元组(E,Q,q0,A,f),其中
E is the input alphabet, a non-empty finite set of symbols
Q is the set of states, non-empty and finite
q0 is the start state, an element of Q
A is the set of accepting or final states, a subset of Q
f is the transition function, taking pairs from Q x E to Q假设我们有两台机器M‘= (E',Q',q0',A',f')和M'’= (E'',Q'',q0'',A'',f'')。为了简化讨论,我们假设E‘= E'’。现在我们将构造M‘,使得L(M') =L(M’)相交(或并或差) L(M'')。
Take E''' = E'' = E'
Take Q''' = Q' x Q''
Take q0''' = (q0', q0'')
Take A''' = (x, y) where x in A' and y in A'' (for union, x in A' or y in A''; for difference, x in A' but not y in A'').
Take f'''((x, y), e) = (f'(x, e), f''(y, e)).就是这样!现在让我们考虑两台机器:一台接受^2n,另一台接受^3n(交集应该是接受^6n的机器...对吧?)。
对于M‘我们有..。
E' = {a}
Q' = {s0, s1}
q0' = s0
A' = {s0}
f'(s0, a) = s1, f'(s1, a) = s0对于M'‘我们有..。
E'' = {a}
Q'' = {t0, t1, t2}
q0'' = t0
A'' = {t0}
f''(t0, a) = t1, f''(t1, a) = t2, f''(t2, a) = t0对于M‘’,我们得到..。
E''' = {a}
Q''' = {(s0, t0), (s0, t1), (s0, t2), (s1, t0), (s1, t1), (s1, t2)}
q0''' = (s0, t0)
A''' = {(s0, t0)} for intersection, {(s0, t0), (s0, t1), (s0, t2), (s1, t0)} for union, {(s0, t1), (s0, t2)} for difference.
f'''((s0, t0), a) = (s1, t1), f'''((s1, t1), a) = (s0, t2), f'''((s0, t2), a) = (s1, t0), f'''((s1, t0), a) = (s0, t1), f'''((s0, t1), a) = (s1, t2), f'''((s1, t2), a) = (s0, t0).这就对了!如果这需要澄清,请让我知道。
https://stackoverflow.com/questions/17721354
复制相似问题