finite-automata - 如何取两个有限自动元的交集

Question

我想要一些关于如何取两个有限自动机相交的例子（带图）。

我已经学会了两个有限自动机的联合。

我在整个互联网上进行了搜索，但没有找到任何东西。

Answer 1

这个想法非常简单，尽管我可以看到混淆的地方。我将通过笛卡尔积机器构造（与您所说的相同）对创建交集（联合，差异）机器的过程进行文本/符号描述关于）。

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)).

给你！现在让我们考虑两台机器：一台接受 a^2n，另一台接受 a^3n（交集应该是一台接受 a^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).

你去吧！请让我知道这是否需要澄清。

资料来源：如何使用交集构造形成DFA？