如何合并两个有限状态自动机？ [英] How to merge two finite state automata?

问题描述

说我有两个确定性的有限状态自动机，它们由以下过渡图表示：

Say I have two deterministic finite state automata represented by the following transition diagrams:

FSA关键字IF： IF

  ___        ___         _
 /   \  I   /   \  F   // \\
>| 0 |----->| 1 |----->||2||
 \___/      \___/      \\_//

ID的FSA： [AZ] [A-Z0-9] *

FSA for an ID: [A-Z][A-Z0-9]*

            ------------
  ___       | _    LET |
 /   \ LET  // \\<------
>| 0 |----->||1||
 \___/      \\_//<------
            |      NUM |
            ------------

我可以使用哪种算法将它们组合成具有三个最终状态的单个确定性有限状态自动机，由以下过渡图表示：

What algorithm may I use to combine them into a single deterministic finite state automata with three final states, represented by the following transition diagram:

            -----------------------
            | LETTER BUT F OR NUM |   --------
  ___       | _          _   LET  v _ |  LET |
 /   \  I   // \\  F   // \\----->// \\<------
>| 0 |----->||1||----->||2||      ||3||<--------
 \___/      \\_//      \\_//----->\\_//<------ |
   |                         NUM  |      NUM | |
   | ANY LETTER OTHER THAN I      ------------ |
   ---------------------------------------------

1: ID
2: IF (IT'S ALSO AN ID, BUT THE KEYWORD IF HAS A HIGHER PRECEDENCE)
3: ID

推荐答案

教科书通常会给自动机 C 这样通过应用 L（C）= L（A）UL（B） = nofollow> de-morgan ，L（C）=（L（A） ^C [交集] L（B） ^C ）< sup> C 。

交集是通过建立笛卡尔乘积自动机来完成的，求反只是在切换接受状态。

构建联合自动机也可以直接完成：构建笛卡尔乘积自动机，最终状态为状态（a，b） a 是 A 或 b 是 B

The textbooks usually gives the automaton C such that L(C) = L(A) U L(B) by applying de-morgan on it, L(C) = (L(A)^C [intersection] L(B)^C)^C.
The intersection is done by building the Cartesian product automaton, and the negation is simply switching the accepting states.
Building the union automaton can also be done directly: Build the Cartesian product automaton, and a final state is a state (a,b) such that a is a final state in the automaton of A OR b is a final state in the automaton of B

自动机中的最终状态。另一种方法是构建不确定的最终自动机（NFA），只需创建一个新状态，并为start（A）和start添加一个epsilon路径（B），并使用标准算法消除自动机中的不确定性。

An alternative is building a Non-Deterministic Final Automaton (NFA) by simply creating a new state, and add an epsilon path for both start(A) and start(B), and use the standard algorithm for eliminating non-determinism from an automaton.

问题-这种自动机将不是最小的（可能远非如此）。您可以尝试对结果使用此算法自动机以使其最小化。

The problem - this automaton will not be minimal (far from it probably). You can try and use this algorithm on the resulting automaton in order to minimze it.

这篇关于如何合并两个有限状态自动机？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！