問題タブ [finite-automata]

まず、これは NFA を DFA に変換するアルゴリズムを求める質問ではありません。

ほとんどの場合、NFA とほぼ同じ数の状態を持つことになりますが、NFA と同等の DFA には最大で 2 ^{n 個の状態があることが知られています (そして証明されています)。}

NFA と同等の DFA が持つ状態数の推定値を予測するにはどうすればよいですか? ^{2 n 個}の状態を持つ同等の DFA を必要とする NFA の特定のタイプはどれですか?

これを尋ねる私の理由は、最小化を考慮せずに、2 ⁿ - 1 状態と「死んだ状態」を確実に生成するいくつかの NFA を「発明」できるようにするためです。

好奇心から、私が使用しているシステムがどの計算モデルと機能的に同等であるかを特定し、その同等性を証明しようとしています。この問題に時間を費やすほど、システムがチューリングと同等ではないことが疑われます。チューリング マシンと再帰的に列挙可能な言語についてはよく理解していますが、機能の少ないオートマトン (プッシュダウン オートマトンなど) についてはよく知らないので、どのように進めればよいかわかりません。

まず、さまざまな計算モデルについて学習するための優れたリソースを推奨できる人はいますか? 文法、言語、オートマトンに興味があり、それらすべての同等性と相違点を証明する方法に興味があります。理想的には、リソースは各モデルのすべての要素を詳細に分析し、それらを比較します。

第二に、システムをこれらの計算モデルのいずれかに当てはめようとするときに使用すべき一般的なアプローチまたはフレームワークはありますか?

試験のために文脈自由文法を準備しています。なぜその言語なのか理解できなかった

は文脈自由ですが、規則的ではありません。なぜ定期的ではないのですか？式が正規でないと言えるのはいつですか?

ありがとう

2つの言語に共通の文字列があるかどうかをテストしたいと思います。これらの言語は両方とも、以下で説明する正規言語のサブセットからのものであり、サンプルの文字列を生成するのではなく、両方の言語に文字列が存在するかどうかを知る必要があるだけです。

言語は、次のようなグロブのような文字列で指定されます

/foo/**/bar/*.baz

ここで、**0個以上の文字に*一致し、そうでない0個以上の文字に一致/し、他のすべての文字はリテラルです。

何か案は？

ありがとう、マイク

編集：

うまく機能しているように見えるものを実装しましたが、正当性の証明はまだ試していません。ソーステストと単体テストを見ることができます

次の形式の関数呼び出しを抽出することになっているステートマシンで作業しています

抽出されたデータはpref("this.is.a.string.which\"can have QUOTES\"", 123456); ファイルからのものです。現在、41kbのファイルを処理するには、このプロセスに1分半近くかかります。この有限状態マシンについて、私がここで真剣に誤解していることはありますか？

ビリー3

編集：まあ、これは私が今まで見た中で最も奇妙なものの1つです。プロジェクトを再構築したところ、かなり正常に実行されています。奇数。

計算理論のコースのメモをいくつか見直していますが、次のステートメントを表示するのに少し行き詰まっており、誰かが説明を手伝ってくれることを望んでいました:)

A を正規言語とする。言語 B = {ab | a は A に存在し、b は A に存在しない*} なぜ B は正規言語なのですか?

いくつかの点は私には明らかです。b が単なる定数文字列である場合、これは自明です。a が A にあり、b が文字列であることはわかっているため、通常の言語は和集合の下で閉じられているため、これら 2 つの文字列を受け入れる言語の和集合は明らかに規則的です。ただし、 b が定数であるかどうかはわかりません。そうかもしれませんし、もしそうなら、これは実際には問題ではありません。意味が分からなくて困っています。ありがとう！

次のFSTを検討してください。

これらの2つのFST（つまり、T1またはT2）で合成操作を実行するにはどうすればよいですか？いくつかのアルゴリズムを見ましたが、あまり理解できませんでした。誰かがそれを簡単な方法で説明できれば、それは大きな助けになるでしょう。

これは宿題ではないことに注意してください。例は、解決策が示されている講義のスライドから取られていますが、私はそれを取得する方法を理解できませんでした。

リカレントニューラルネットのチューリング完全性に関するいくつかの論文（例：ニューラルネットを使用したチューリング計算可能性、HavaT.SiegelmannおよびEduardoD.Sontag、1991）を読んでいると、そこで与えられた証明は実際にはそうではないと感じました。実用的。たとえば、参照されている論文には、ニューロンの活動が無限に正確でなければならないニューラルネットワークが必要です（有理数を確実に表すため）。他の証明には、無限のサイズのニューラルネットワークが必要です。明らかに、それは実際にはそれほど実用的ではありません。

しかし、私は今、チューリング完全性を求めることがまったく意味があるのか​​どうか疑問に思い始めました。厳密な定義によれば、今日のチューリング完全なコンピューターシステムはありません。これは、無限のテープをシミュレートできるコンピューターシステムがないためです。

興味深いことに、プログラミング言語の仕様は、チューリング完全であるかどうかにかかわらず、ほとんどの場合オープンのままです。結局のところ、彼らが常により多くのメモリを割り当てることができるかどうか、そして関数呼び出しのスタックサイズが無限であるかどうかという問題に要約されます。ほとんどの仕様は実際にはこれを指定していません。もちろん、ここでは利用可能なすべての実装が制限されているため、プログラミング言語のすべての実用的な実装はチューリング完全ではありません。

つまり、すべてのコンピューターシステムは、有限状態マシンと同じくらい強力であり、それ以上ではないということです。

そして、それは私に質問をもたらします：チューリングという用語は完全にどれほど有用ですか？

そしてニューラルネットに戻る：ニューラルネット（私たち自身の脳を含む）の実際の実装では、無限の数の状態を表すことはできません。つまり、チューリング完全性の厳密な定義によって、チューリング完全ではありません。では、ニューラルネットがチューリング完全であるかどうかという質問はまったく意味がありますか？

それらが有限状態マシンと同じくらい強力であるかどうかという質問は、すでにずっと以前に回答されており（1954年、ミンスキーによる回答、もちろん：はい）、回答も簡単なようです。つまり、少なくとも理論的には、それはすでに他のコンピュータと同じくらい強力であるという証拠でした。

私が本当に知りたいことについてのいくつかの他の質問：

• コンピュータの計算能力についてより具体的なことを言うことができる理論用語はありますか？（限られたメモリスペースを考えると）

• ニューラルネットの実際の実装の計算能力をコンピューターとどのように比較できますか？（チューリング完全性は、上記で論じたように有用ではありません。）

FSM（EDIT：Finite State Machine）状態をどのように実装しますか？私は通常、FSMを一連の関数、ディスパッチャー、スレッドのように、現在の実行状態を示すものと考えています。つまり、状態を表す関数/ファンクターへの呼び出しをブロックします。

ちょうど今、私は別のスタイルで1つを実装しました。ここでは、関数（オブジェクト）で状態を表しますが、スレッドはstate->step()メソッドを呼び出すだけで、できるだけ早く戻ります。状態が終了し、遷移が発生する必要がある場合は、それに応じてそれを示します。関数はほとんど次のように見えるので、これを「ポーリング」スタイルと呼びます。

FSM内のFSMであることを認識しています。

かなり単純に感じますが、特定の利点があります。スレッドがブロックされたり、ある種の while (!CanGoForward)checkGoForward(); ループに保持されたりするのは面倒で扱いにくい場合がありますが、ポーリングはデバッグがはるかに簡単であると感じました。これは、FSMオブジェクトがすべてのステップの後に制御を取り戻すためであり、デバッグ情報を出力するのは簡単です。

さて、私は私の質問から逸脱しています：FSMの状態をどのように実装しますか？