Compiler-design-finite-automata
提供：Dev Guides
コンパイラ設計-有限オートマトン
有限オートマトンは、入力としてシンボルの文字列を受け取り、それに応じて状態を変更する状態マシンです。 有限オートマトンは、正規表現の認識機能です。 正規表現文字列が有限オートマトンに入力されると、リテラルごとに状態が変わります。 入力文字列が正常に処理され、オートマトンが最終状態に到達した場合、それは受け入れられます。つまり、供給された文字列は、手元の言語の有効なトークンであると言われました。
有限オートマトンの数学的モデルは以下で構成されています：
- 状態の有限集合（Q）
- 入力シンボルの有限集合（Σ）
- 1つの開始状態（q0）
- 最終状態のセット（qf）
- 遷移関数（δ）
遷移関数（δ）は、状態の有限集合（Q）を入力シンボルの有限集合（Σ）にマッピングします。Q×Σ➔Q
有限オートマトンの構築
L（r）を、ある有限オートマトン（FA）によって認識される通常の言語とします。
- 州：FAの州は円で表されます。 州名は円の中に書かれています。
- 開始状態：オートマトンが開始する状態は、開始状態と呼ばれます。 開始状態には矢印があります。
- 中間状態：すべての中間状態には少なくとも2つの矢印があります。 1つはそれらを指し、もう1つはそれらを指します。
- 最終状態：入力文字列が正常に解析された場合、オートマトンはこの状態にあると予想されます。 最終状態は二重丸で表されます。 それはそれを指す任意の奇数の矢印とそれから外を指す偶数の矢印を持つことができます。 奇数の矢印の数は偶数よりも1つ多い、つまり *奇数=偶数+ 1 *。
- 遷移：ある状態から別の状態への遷移は、入力で目的のシンボルが見つかったときに発生します。 移行すると、オートマトンは次の状態に移行するか、同じ状態を維持できます。 ある状態から別の状態への移動は、矢印が目的の状態を指す矢印として示されます。 オートマトンが同じ状態のままである場合、状態からそれ自体を指す矢印が描かれます。
例：FAが数字1で終わる3桁のバイナリ値を受け入れると仮定します。 FA = \ {Q（q〜0〜、q〜f〜）、Σ（0,1）、q〜0〜、q〜f〜、δ}
