形式語言

計算機科學中複雜性的概念核心是形式語言的概念。形式語言是一組詞語，這些詞語是從一個有限的符號集（通常稱為 $\Sigma$ ）中提取的有限長度字串。我們研究定義特定語言的機器的計算複雜性，這些機器透過**接受**或**拒絕**其字母表中的每個可能的詞語來定義該語言。

雖然語言中的每個詞語都必須是有限的，但語言可能包含任意長度的詞語，因此可能包含無限個詞語。例如，從字母表 $\Sigma =\{a,b\}$ 中提取的所有字串的集合，其中包含一定數量的 a，後跟相同數量的 b。因此，該語言包含任何形式為 $a^{n}b^{n}$ 的字串，其中 $a^{n}$ 是重複 n 次的符號 a。由於 n 可以是任何正整數，因此該語言中必須有無限個詞語。

許多形式語言都有與之關聯的生成語法，生成語法是一組替換規則，這些規則包含三種類型的符號：ε，表示空字串（長度為 0 的字串）；非終結符，這些符號不在語言的字母表中；終結符，這些符號在語言的字母表中。按照慣例，非終結符通常是大寫字母，而終結符（以及相關的形式語言的字母表）通常是小寫字母。語法還包括一個稱為起始符號的非終結符，這是替換規則在任何替換髮生之前假設存在的符號。透過對何時應用哪個替換規則進行選擇，起始符號可以轉換為與該語法關聯的語言中的任何詞語，而不能轉換為其他詞語，這就是為什麼該語法被稱為生成語言的原因。這些替換規則如何形成取決於所涉及的語言類別，並且對語法的每組限制都會建立一個生成語法的類別。並非所有形式語言類別都與生成語法類別相關聯。

通常與語言類別相關的另一個物件是識別機器。這些機器如何操作以及它們的限制是什麼取決於它們所對應的語言類別，但如果機器在給定該語言中的任何詞語作為輸入時，總是“接受”該詞語，並且永遠不會“接受”不在該語言中的詞語，則稱該機器識別該語言。並非所有形式語言類別都與識別機器型別相關聯，但計算機科學家研究的大多數語言都與識別機器型別相關聯。

有多個不同語言類別，每個類別都基於其包含的語言的複雜性。最著名的語言類別是喬姆斯基層次的四個類別，這些類別由諾姆·喬姆斯基在其 1959 年的論文“關於語法的一些形式屬性”中定義 1。有關其他語言類別的資訊，請參閱章節其他語言類別。

總結

一個字母表是有限的符號集合。
一個詞語是從字母表中提取的有限長度的符號串。
一個形式語言是一組詞語。
一個生成語法是一組替換規則，這些規則允許您從起始符號建立語言中的任何詞語（以及其他詞語）。
一個識別機器是“接受”語言中的任何詞語（以及其他詞語）的機器。
一個語言類別是一組複雜性相似的語言，因此它們具有相似的生成語法型別和相似的識別機器型別。