首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何求两个有限自动机的交

问如何求两个有限自动机的交
EN

Stack Overflow用户
提问于 2013-07-18 18:47:34
回答 1查看 1.6K关注 0票数 1

我想要一些例子,如何采取两个有限自动机的交集(与图表)。

我学会了取两个有限自动机的并集。

我在互联网上找遍了,但什么也没找到。

EN

回答 1

Stack Overflow用户

发布于 2013-11-04 21:48:04

这个想法非常简单,尽管我可以看到混淆的原因。我将通过笛卡尔乘积机器构造(与您所说的相同),对制造交集(并集,差集)机器的过程进行文本/符号描述。

DFA是一个5元组(E,Q,q0,A,f),其中

代码语言:javascript
复制
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'')。

代码语言:javascript
复制
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‘我们有..。

代码语言:javascript
复制
E' = {a}
Q' = {s0, s1}
q0' = s0
A' = {s0}
f'(s0, a) = s1, f'(s1, a) = s0

对于M'‘我们有..。

代码语言:javascript
复制
E'' = {a}
Q'' = {t0, t1, t2}
q0'' = t0
A'' = {t0}
f''(t0, a) = t1, f''(t1, a) = t2, f''(t2, a) = t0

对于M‘’,我们得到..。

代码语言:javascript
复制
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).

这就对了!如果这需要澄清,请让我知道。

来源:How to use the intersection construction to form a DFA?

票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/17721354

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档