computer-science - 学习计算模型的好资源？

Question

出于好奇，我试图确定我使用的系统在功能上等效于哪种计算模型，并证明等效性。我在这个问题上花的时间越长，我就越怀疑这个系统不是图灵等效的。我对图灵机和递归可枚举语言的理解很好，但我对功能较弱的自动机(例如下推自动机)知之甚少，所以我不确定如何进行。

首先，谁能推荐一个学习不同计算模型的好资源？我对语法、语言和自动机以及如何证明它们之间的等价性和差异性很感兴趣。理想情况下，资源将非常详细地分解每个模型的所有元素并进行比较。

其次，在尝试将系统拟合到任何这些计算模型时，是否应该使用通用方法或框架？

Answer 1

我会推荐一本关于计算机科学的好教科书(在我的大学类(class)中，我正在学习 Sipser's Introduction to the Theory of Computation，我认为这非常好。您可能还会找到教同样内容的 free textbook，但是我没有任何经验，所以我不能推荐)。

另一种方法可能只是阅读维基百科。如果您知道要查找的内容以及查找的顺序，您实际上可以从维基百科文章中获得很多帮助。此外，如果有任何不清楚的地方，您通常可以通过 Google 搜索并找到有关该特定主题的更多资源。

当然，这不如真正的教科书，但它是现在开始的好地方，而且它是免费的。

作为起点，我建议阅读以下主题(按列出的顺序):

1. Deterministic Finite Automaton
2. Nondeterministic Finite Automaton ，以及它们与 DFA 的等价性。
3. Regular Languages ，以及它们与 DFA 的等价性。
4. Pushdown Automata
5. Context-free Grammars ，以及它们与下推自动机的等价性。
6. Chomsky Hierarchy
7. Turing Machines

这应该对人们谈论的大多数计算模型进行了非常简短的介绍。 2 : 我会推荐一本很好的计算机科学教科书(在我的 Uni 类(class)中，我正在学习 Sipser's Introduction to the Theory of Computation，我认为这非常好)。另一种方法可能只是阅读维基百科。如果您知道要查找的内容以及查找的顺序，您实际上可以从维基百科文章中获得很多帮助。此外，如果有任何不清楚的地方，您通常可以通过谷歌搜索并找到有关该特定主题的更多资源。作为起点，我建议阅读以下主题(按列出的顺序): 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