5

次の遷移図で表される 2 つの決定論的有限状態オートマトンがあるとします。

キーワード IF の FSA: IF

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

ID の FSA: [AZ][A-Z0-9]*

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

次の遷移図で表される、3 つの最終状態を持つ単一の決定論的有限状態オートマトンにそれらを結合するために、どのアルゴリズムを使用できますか?

            -----------------------
            | 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
4

1 に答える 1

5

教科書は通常、ド・モルガンを適用することにより、L（C）=（L（A）C [交差点]L（B）C）CCとなるようなオートマトンを提供します。 交差はデカルト積オートマトンを構築することによって行われ、否定は単に受け入れ状態を切り替えることです。 ユニオンオートマトンの構築も直接行うことができます。デカルト積オートマトンを構築します。最終状態は、のオートマトンの最終状態であるか、のオートマトンの最終状態であるような状態です。L(C) = L(A) U L(B)

(a,b)aAbB

別の方法は、新しい状態を作成するだけで非決定性最終オートマトン（NFA）を構築し、start（A）とstart（B）の両方にイプシロンパスを追加し、標準アルゴリズムを使用してオートマトンから非決定性を排除することです。 。

問題-このオートマトンは最小ではありません（おそらくそれからはほど遠いです）。最小化するために、結果のオートマトンでこのアルゴリズムを試して使用することができます。

于 2012-06-26T06:44:12.243 に答える