module - 我在哪里可以找到关于可计算性和复杂性的良好解释？

Question

我在 Computability and Complexity 有一个重复出现，我想知道是否有人有很好的资源来进行这种研究。诸如常规语言、上下文无关和上下文敏感语言之类的东西。

例如：

如您所见，这是一个措辞可怕的问题。我们的讲师给我们的笔记同样糟糕。我真的需要通过这个模块，所以如果有人有很好的资源来研究这些主题，我将不胜感激。

Answer 1

我认为您遇到的问题不是措辞的错误，而是您还不能适应所涉及的数学符号这一事实。

维基百科有很多关于自动机和其他计算机科学理论主题的文章。此外，在“NFA 到 DFA”上进行谷歌搜索会发现许多有用的结果。自动机在编译器中大量使用，因此您可能会从编译器课程中找到对材料中事物的更“实用”的解释。

但是，您的课程将是大量数学课程，因此您最好放下对您所获得的材料很差的态度，花时间学习理解它，从而为自己做到最好。数学公式为您提供精确而简洁的描述，而不会像非正式语言那样有太多的误解空间。

Answer 2

您可能想查看 Avi Kak 在 https://engineering.purdue.edu/kak/courses-i-teach/ECE664/Index.html
上提供的课堂笔记 请 参阅第 17 课的手写笔记，其中解释了你的问题。