Как объединить два конечных автомата?

Предположим, что у меня есть два детерминированных автомата конечного состояния, представленных следующими диаграммами переходов:

FSA для ключевого слова IF: IF

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

FSA для идентификатора: [A-Z][A-Z0-9]*

            ------------
  ___       | _    LET |
 /    LET  // \<------
>| 0 |----->||1||
 ___/      \_//<------
            |      NUM |
            ------------
Какой алгоритм я могу использовать, чтобы объединить их в один детерминированный конечный автомат с тремя конечными состояниями, представленными следующей диаграммой переходов: 
            -----------------------
            | 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
1 4
algorithm finite-state-machine finite-automata

1 ответ:

Учебники обычно дают автомат C такой, что L(C) = L(A) U L(B) применяя к нему де-Моргана , L (C) = (L (A) C [пересечение] L (B) C)C . Пересечение выполняется путем построения автомата декартова произведения, а отрицание-это просто переключение принимающих состояний.
построение автомата объединения также может быть выполнено непосредственно: построить автомат декартова произведения, и конечным состоянием является состояние (a,b) такое, что a является конечным состоянием в автомат A или b является конечным состоянием в автомате B

Альтернативой является построение недетерминированного конечного автомата (NFA) путем простого создания нового состояния и добавления пути Эпсилона как для start(A), так и для start(B), а также использование стандартного алгоритма для устранения недетерминизма из автомата.

Проблема - этот автомат не будет минимальным (далеко не обязательно). Вы можете попробовать использовать этот алгоритм на результирующем автомате в для того, чтобы свести его к минимуму.

4