1

オートマトンを学び始めたところです。DFAを考えると理解しやすく、設計するのもそれほど難しくないようです。しかし、私は物事を証明するのは非常に難しいと感じています...

誰かがこの質問またはいくつかのヒントの非公式な証拠を与えることができますか？どうもありがとう！

PS：申し訳ありませんが、はっきりと表現していませんでした。@Danが言ったことは、まさに私が言っていることです。

「文字列wが与えられた場合、オートマトンはwを受け入れるか拒否するか」という質問を決定する理由 線形時間で実行できますか？

4

2 に答える 2

4

このように考えてみてください：

  1. 入力文字列の各文字はDFAによって何回読み取られますか？
  2. 入力から1文字を処理する場合、DFAはどのくらいの作業を行いますか？

お役に立てれば！

于 2013-01-20T19:58:01.343 に答える
4

「文字列 w が与えられた場合、オートマトンは w を受け入れるか拒否しますか?」という質問を決定する理由を知りたいと思います。線形時間で実行できますか?

w=a_1...a_n とします。初期状態 q_0 から開始し、遷移 \delta(q_0, a_1) = q_1 を適用すると、q_1 になります。最後の文字を処理するまで、これを n 回繰り返します。これは線形時間アルゴリズムです ;)

于 2013-01-20T19:58:55.400 に答える