3

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

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

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

4

3 に答える 3

3

次のリンクからのビデオ講義は、計算理論の優れた紹介を提供します。これは、このトピックに関する最高のリソースの 1 つです。

Shai Simonson 教授による計算理論のビデオ講義

于 2010-01-12T08:03:40.910 に答える
2

コンピューター サイエンスの優れた教科書をお勧めします (大学のコースでは、シプサーの計算理論入門から勉強しています。これは私の意見では非常に優れています。同じことを教えている無料の教科書も見つかるかもしれませんが、経験がないのでお勧めできません。）

他のアプローチは、おそらくウィキペディアを読むことです。何をどのような順序で探しているかを知っていれば、ウィキペディアの記事から実際に多くのマイレージを得ることができます。また、不明な点がある場合は、通常、Google で検索して、その特定のテーマに関するリソースをさらに見つけることができます。

もちろん、これは実際の教科書ほど優れたものではありませんが、今すぐ始めるのに適した場所であり、無料です。

出発点として、次のトピックを (記載されている順序で) 読むことをお勧めします。

  1. 決定論的有限オートマトン
  2. 非決定性有限オートマトン、およびそれらの DFA との等価性。
  3. 正規言語、および DFA と同等の言語。
  4. プッシュダウンオートマトン
  5. Context-free Grammars、および Pushdown Automata と同等のもの。
  6. チョムスキー階層
  7. チューリングマシン

これで、人々が話題にしている計算モデルのほとんどを簡単に紹介できるはずです。 2 : コンピューター サイエンスの優れた教科書をお勧めします (大学のコースでは、シプサーの計算理論入門から勉強していますが、これは私の意見では非常に優れています)。他のアプローチは、おそらくウィキペディアを読むことです。何をどのような順序で探しているかを知っていれば、ウィキペディアの記事から実際に多くのマイレージを得ることができます。また、不明な点がある場合は、通常、Google で検索して、その特定のテーマに関するリソースをさらに見つけることができます。出発点として、次のトピックについて読むことをお勧めします (記載されている順序で): 1. 1 :http://www.amazon.com/Introduction-Theory-Computation-Second-Michael/dp/0534950973/ref=sr_1_1?ie=UTF8&s=books&qid=1263282346&sr=8-1

于 2010-01-12T07:58:19.017 に答える
1

見つけるのが難しいかもしれない古いテキストは、Hopcroft と Ullman の「Automata Theory, Languages, and Computation の紹介」です。いくつかのエディションがあります --- '79 は、複雑なものを導入する際のパンチが最も少ないという点で、最高であると聞いています。小さいながらも正統な教科書であり、探しているものだけでなく、その分野全体を紹介しています。おそらく、他の情報源が除外している「トリッキーな」証拠の1つがあなたの鍵になるかもしれないという無駄な希望に基づいて、これを提案します.

より穏やかな出発点として、便利な「ベンチマーク」言語がいくつかあります。

  • モデルが文字列内に同じ数の A と B があるすべての文字列の言語を認識できる場合、少なくとも FSM よりも強力です。
  • できない場合は、FSM と同等である可能性があります。
  • 同様に、モデルが文字列内の A、B、および C の数が同じであるすべての文字列の言語を認識できる場合、そのモデルはCFG または PDA よりも強力です。

これらの「ベンチマーク言語」は実際には変装した関数にすぎません --- 最初の言語は基本的に 2 つの単項数が等しいかどうかを尋ね、2 つ目は 3 つの単項数が等しいかどうかを尋ねます。それらは素晴らしくシンプルで、特定のモデルの機能を上回ったり下回ったりすることはよく知られています。より複雑なマシン用の単純なものは知らないので、自分でできるかもしれません。

線形境界オートマトンであるモデル「LBA」の場合、TM で計算可能であるが LBA ではない既知の自然言語はないと私は信じています。この声明はぼんやりとした記憶から引き出されたものであるため、正式な証拠と見なさないでください. :)

（最後に）「ベンチマーク」言語は平等を確立していないことに注意してください。つまり、モデルが 2 つの単項数を比較できない場合でも、それが必ずしも FSM と同等であることを意味するわけではなく、さらに弱い可能性があります。言語は、それが力よりも大きいか、力よりも小さいかを確立するだけです。

完全に (完全に) 異なる方向で、Sipser の本は正規表現と FSM の間、および PDA と CFG の間の同等性の証明を行っています。あなたが検討している計算モデルの種類についてかなり曖昧であるため、それがどれほど役立つかはわかりませんが、同等性に固執している場合は、それらが良い出発点になる可能性があります。

于 2010-01-14T05:38:52.863 に答える