我试图理解四种不同的乔姆斯基语言类型，但我发现的定义对我来说并没有什么意义。我知道类型0是自由语法，类型1是上下文敏感的，类型2是上下文无关的，而类型3是正则的。所以，有人能解释一下并把它放在上下文中吗，谢谢。
语言是属于该语言的一组单词。然而，很多时候，与其列出语言中的每一个单词，不如指定一组生成该语言单词的规则(并且仅指定这些规则)来识别所讨论的语言。
注意：可以有多个规则集来定义相同的语言。
一般来说，对规则的限制越多，语言的表达能力就越差(从规则中生成的单词就越少)，但如果一个单词属于规则指定的语言，则更容易识别。由于后者，我们希望识别对其规则限制最多的语言，这些规则仍然允许我们生成相同的语言。
关于规则的几句话：通常，您描述一种具有四项(也称为四元组)的形式语言：
- 一组非终端符号(N)
- 终端符号集(T)
- 生成规则集(P)
- 开始符号(S)
终端符号(AKA字母)是一种语言的单词所包含的符号，通常是小写英文字母的子集(例如"a"、"b"、"c")
非终端符号标记单词生成中的中间状态，指示可能的变换仍然可以应用于中间"状态"；单词"；。终端符号和非终端符号之间没有重叠(即，两个集合的交集为空)。用于非终端的符号通常是大写英文字母的子集(例如"A"、"B"、"C")
规则表示一系列终端符号和非终端符号上的可能变换。它们的形式为：左侧->右侧，其中左侧和右侧都由一系列端子符号和非端子符号组成。一个示例规则：aBc->cBa，这意味着一系列符号"；aBc"；(作为中介词"words"的一部分)可以被替换为"series"；cBa"；在单词的生成过程中。
起始符号是一个专用的非终端符号(通常用S表示)；根"；或"；"开始"；即在一系列字生成中应用的第一规则总是将起始符号作为其左侧。
当所有非词尾都被词尾取代时，一个词的生成就成功结束了(因此最后的"中间词"只由词尾符号组成，这表明我们得到了所讨论语言的一个词)。
当不是所有的非终端都被终端取代，但没有可以应用于当前中介的产生规则时，单词的生成是不成功的；单词"；。在这种情况下，生成必须从起始符号开始重新开始，遵循生成规则应用程序的不同路径。
示例：
L={T，N、p和S}，
其中
T={a，b，c}
N=｛A，B，C，S｝
p={S->A，S->AB，S->BC，A->A，B->bb，C->ccc}
表示三个词的语言："；a"abb"；以及"；bbccc"；
规则应用示例：
S->AB->aB->abb
其中，我们1)从起始符号(S)开始，2)应用第二条规则(用AB替换S)，3)应用第四条规则(将A替换为A)，4)应用第五条规则(以bb替换B)。由于在产生的"终端"中没有非终端；abb"；，它是语言中的一个词。
在一般讨论规则时，希腊符号alpha、beta和gamma等表示(可能为空)一系列终端+非终端符号；希腊字母epsilon表示空字符串(即空的符号序列)。
Chomsky层次结构中的四种不同类型描述了具有不同表达能力的语法(对规则的不同限制)。
-
由Type0(或Unrestricted)语法生成的语言最具表达性(限制较少)。递归枚举语言集包含可以使用图灵机(基本上是计算机)生成的语言。这意味着，如果你有一种比这种类型更具表达力的语言(例如英语)，你就无法编写一种算法来列出该语言的每一个(并且只能列出这些)单词。规则有一个限制：规则的左侧不能为空(不能突然引入任何符号)。
-
类型1(上下文相关)语法生成的语言是语境相关lphaAbeta->α-γ-β，其中α和β可以为空，γ不为空(例外：S->ε规则，只有当开始符号S没有出现在任何规则的右侧时才允许)。这限制了规则在其左侧具有至少一个非终端，并允许它们具有"非终端"；上下文"：只有当非终端A被("is in the context of")alpha和beta包围时。规则的应用保留上下文(即alpha和beta不会更改)。
-
类型2(上下文无关)语法生成的语言是无上下文语言。规则具有以下形式的限制：A->伽玛。这限制了规则在其左侧恰好有一个非终端；上下文"；。这本质上意味着，如果你在中间词中看到一个非终端符号，你可以应用任何一个左侧有该非终端符号的规则，将其替换为右侧，而不考虑非终端符号周围的环境。大多数编程语言都有上下文无关的生成语法。
-
由Type3(Regular)语法生成的语言是Regular语言。规则具有以下形式的限制：A->a或a->aB(如果起始符号S没有出现在任何规则的右侧，则允许规则S->ε)，这意味着每个非终端必须恰好产生一个终端符号(也可能产生一个非终端符号)。正则表达式生成/识别此类型的语言。
可以取消/修改其中的一些限制，以保持修改后的语法具有相同的表达能力。修改后的规则可以允许其他算法识别一种语言的单词。
请注意(如前所述)一种语言通常可以由多个语法(甚至是属于不同类型的语法)生成。一个语系的表达能力通常等同于可以生成这些语言的最严格语法类型的表达能力(例如，由正则(第3类)语法生成的语言也可以由第2类语法生成，但它们的表达能力仍然是第3类语法的表达能力)。
示例
正则语法
T={a，b}
N={A，B，S}
p={S->aA，A->A A，A->aB，B->bB，B->B}
生成语言，该语言包含以非零数量的"a"开头、后跟非零数量"b"的单词。请注意，用正则语法描述一种语言是不可能的，其中每个单词都由一个数量相同的"a"和一个数量相等的"b"组成。
上下文无关语法
T={a，b}
N={A，B，S}
p={S->ASB，A->A，B->B}
生成语言，该语言包含以非零数量的"a"开头，后跟相等数量的"b"的单词。请注意，不可能用上下文无关语法来描述一种语言，其中每个单词由多个"a"组成，后面跟着相等数量的"b"，后面跟着相同数量的"c"。
上下文敏感语法
T={a，b，c}
N=｛A，B，C，H，S｝
p={S->aSBC，CB->HB，HB->HC，HC，BC，aB->aB，bB->bB，BC->BC，cC->cC}
生成一种语言，该语言包含以非零数量的"a"开头，后跟相等数量的"b"，后跟相等数目的"c"的单词。H在这个语法中的作用是使"；交换"；CB组合到BC组合，所以B可以聚集在左边，C可以聚集在右边。请注意，不可能用上下文敏感语法来描述一种语言，其中单词由一系列"a"组成，其中"a"的数量是素数，但可以编写一个不受限制的语法来生成该语言。
有4种类型的语法
类型0：
-
无限制语法接受的语法
-
递归可枚举语言接受的语言
-
自动机是图灵机
类型-1：
-
上下文敏感语法接受的语法
-
上下文敏感语言接受的语言
-
自动机是线性有界自动机
类型2：
-
上下文无关语法接受的语法
-
上下文无关语言接受的语言
-
自动机是PushDown自动机
类型3：
-
正则语法接受的语法
-
常规语言接受的语言
-
自动机是有限状态自动机
-
Chomsky是一个正规形式，每个产品都有形式：
- A->BC或A->A
中的规则可以有两个变量或只有一个终端乔姆斯基