形式語言、自動機和計算理論/前言

為什麼要學習自動機、語言和計算 (ALC) 理論？它不是一個高調的研究領域，也不是一個應用領域，儘管其中一些材料是計算的“麵包和黃油”，是“螺母和螺栓”——如此普遍以至於對許多人來說是不可見的。也就是說，它是一門基礎課程。我很高興，我認為，我們學習 ALC 是因為它對那些對計算感興趣的人來說很有吸引力和有趣。在它的抽象中，你會發現純粹的計算理論和計算思維的練習。就像你作為一名計算學生上的一門人文課一樣，如果你對計算的職業傾向有強烈的興趣，並且你仍然要學習這方面的材料，我建議你相信你所學到的東西有一些（或者很多）將在以後派上用場。我說“相信”是因為理論和應用之間的聯絡可能不像你在一本演算法文字中看到的那樣在本文中那麼明顯。當然，ALC 與演算法、程式語言和人工智慧之間存在概念聯絡，本書將對此進行探討。

我於 1979 年從 Dov Harel 博士生那裡學習了“這門課”，我認為它很美——我認為抽取引理是人生的隱喻。這個領域並沒有太大變化（基礎沒有太大變化，或者可能很少變化），儘管人工智慧對計算領域的衝擊以及對其他公眾的衝擊，導致了對深度學習框架如何融入經典計算理論的新分析，深度學習框架目前在人工智慧和機器學習中佔據主導地位。雖然這本書涉及到最近關於人工智慧的研究以及人工智慧的經典材料，但它在處理形式語言、語法、自動機和計算的理論方面基本上是傳統的。

也許你會對 ALC 產生類似於我的反應（以及其他反應）——它對計算的崇拜，因為它是一個提供更深智慧的領域，而不僅僅是體現為最新小工具的掌握，而是主要源於對計算早期核心抽象的讚賞。

本書的目標是將 ALC 的處理“簡化”到我通常在一學期課程中涵蓋的內容，採用我喜歡的組織方式，並增加了對應用的處理，包括人工智慧 (AI)。我對這一領域的瞭解源於本科學習以及在這一領域教授本科生，主要使用 Hopcroft 和 Ullman 的教科書，不過我將個人見解融入到處理中，以及處理 ALC 與人工智慧和機器學習的關係。練習通常取自其他來源，並註明出處。我也添加了其他練習。

我的原創練習中獨特地包括一些要求學生與人工智慧互動以討論材料並審查這些互動的練習。像我這樣的教師，雖然不是該領域的科研人員，但仍然熱愛它，可能會認識到我對與人工智慧討論這些材料的興趣——在日常生活中，我還能與誰談論它呢？！與人工智慧的大型語言模型的互動為學生提供了一個機會來討論 ALC——它的方法、概念和哲學——以他們以前從未有過的方式。這些人工智慧改變了人類現在與計算機互動的方式，它們有可能奪走我們曾經擁有的計算機科學家獨特技能集之一——與世界上最愚蠢的能夠做出反應的實體交流的能力！我說“奪走我們”是因為這些計算機似乎一天比一天不那麼愚蠢。在我看來，計算機科學家是或應該是世界上最好的溝通者之一。溝通的方式，即程式語言，不再是必需的，但至少在可預見的未來，一些良好的溝通原則，如對你的談話夥伴知道什麼或相信什麼做出假設的危險，仍然是相關的。關於與人工智慧進行 ALC 材料對話的練習要求學生分析、除錯、擴充套件、專業化以及以其他方式詢問他們的討論。