Как слить два автомата с конечным состоянием?

Question

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

FSA для ключевого слова ЕСЛИ: ЕСЛИ

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

FSA для ID: [AZ] [А-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 

Answer 1

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

Альтернативой является создание Non-Deterministic Final Automaton (NFA) путем простого создания нового состояния и добавления пути epsilon для запуска (A) и запуска (B) и использования стандартного алгоритма для устранения недетерминизма с автомата.

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