形式语言、自动机和计算理论/前言

为什么要学习自动机、语言和计算 (ALC) 理论？它不是一个高调的研究领域，也不是一个应用领域，尽管其中一些材料是计算的“面包和黄油”，是“螺母和螺栓”——如此普遍以至于对许多人来说是不可见的。也就是说，它是一门基础课程。我很高兴，我认为，我们学习 ALC 是因为它对那些对计算感兴趣的人来说很有吸引力和有趣。在它的抽象中，你会发现纯粹的计算理论和计算思维的练习。就像你作为一名计算学生上的一门人文课一样，如果你对计算的职业倾向有强烈的兴趣，并且你仍然要学习这方面的材料，我建议你相信你所学到的东西有一些（或者很多）将在以后派上用场。我说“相信”是因为理论和应用之间的联系可能不像你在一本算法文本中看到的那样在本文中那么明显。当然，ALC 与算法、编程语言和人工智能之间存在概念联系，本书将对此进行探讨。

我于 1979 年从 Dov Harel 博士生那里学习了“这门课”，我认为它很美——我认为抽取引理是人生的隐喻。这个领域并没有太大变化（基础没有太大变化，或者可能很少变化），尽管人工智能对计算领域的冲击以及对其他公众的冲击，导致了对深度学习框架如何融入经典计算理论的新分析，深度学习框架目前在人工智能和机器学习中占据主导地位。虽然这本书涉及到最近关于人工智能的研究以及人工智能的经典材料，但它在处理形式语言、语法、自动机和计算的理论方面基本上是传统的。

也许你会对 ALC 产生类似于我的反应（以及其他反应）——它对计算的崇拜，因为它是一个提供更深智慧的领域，而不仅仅是体现为最新小工具的掌握，而是主要源于对计算早期核心抽象的赞赏。

本书的目标是将 ALC 的处理“简化”到我通常在一学期课程中涵盖的内容，采用我喜欢的组织方式，并增加了对应用的处理，包括人工智能 (AI)。我对这一领域的了解源于本科学习以及在这一领域教授本科生，主要使用 Hopcroft 和 Ullman 的教科书，不过我将个人见解融入到处理中，以及处理 ALC 与人工智能和机器学习的关系。练习通常取自其他来源，并注明出处。我也添加了其他练习。

我的原创练习中独特地包括一些要求学生与人工智能互动以讨论材料并审查这些互动的练习。像我这样的教师，虽然不是该领域的科研人员，但仍然热爱它，可能会认识到我对与人工智能讨论这些材料的兴趣——在日常生活中，我还能与谁谈论它呢？！与人工智能的大型语言模型的互动为学生提供了一个机会来讨论 ALC——它的方法、概念和哲学——以他们以前从未有过的方式。这些人工智能改变了人类现在与计算机互动的方式，它们有可能夺走我们曾经拥有的计算机科学家独特技能集之一——与世界上最愚蠢的能够做出反应的实体交流的能力！我说“夺走我们”是因为这些计算机似乎一天比一天不那么愚蠢。在我看来，计算机科学家是或应该是世界上最好的沟通者之一。沟通的方式，即编程语言，不再是必需的，但至少在可预见的未来，一些良好的沟通原则，如对你的谈话伙伴知道什么或相信什么做出假设的危险，仍然是相关的。关于与人工智能进行 ALC 材料对话的练习要求学生分析、调试、扩展、专业化以及以其他方式询问他们的讨论。