automation - 文字列を受け入れない有限オートマトン

Question

有限オートマトン over(0,1) が文字列を受け入れないのはどうしてですか? としか思えない

s->a->q->F

ここで、最終状態 F は空集合です。それは本当ですか？

Answer 1

答えはイエスです。なぜ「最も可能性が高い」のですか？良い。

数学的には、FSA は 5 タプル(Sigma, S, s0, delta, F)です。

• Sigmaはアルファベット、
• Sは状態の集合であり、
• s0は初期状態、
• deltaは状態遷移関数、
• F受け入れ状態のセットです。

を修正したのでSigma、問題が発生する可能性のある場所は 4 か所しかありません。FSA を手動で作成する場合は、もちろん作成します。

• 状態を持たない
• 初期状態を持たない
• すべての州にアクセスできるわけではない
• 受け入れ状態を持たない

整形式の FSA (S空でないことを意味し、すべての状態にアクセスできることを意味します) を想定する場合、たとえばfomas0 in Sのようなライブラリを使用した正規表現から作成する場合は、そうです: FSA が文字列を受け入れないということは、受け入れ状態を持たないということです。