乔姆斯基层级

乔姆斯基层级（Chomsky Hierarchy）是个关于语言难度的分类法，1956年由语言学家诺姆·乔姆斯基搞出来的。他当时想弄明白，哪些语言能被机器识别，哪些不能，就把语言分成四层，从简单到复杂，像搭积木一样一层比一层高。它最早是为了研究语言和机器的数学关系诞生的。

四个层级及其特征

1. 类型0：无限制语法（递归可枚举语言）

   • 生成能力：可生成所有能被图灵机识别的语言，涵盖最广泛的计算可能性，包括所有可计算语言。
   • 自动机：图灵机。
   • 规则特点：语法规则无任何限制，允许任意形式的替换。

2. 类型1：上下文敏感语法

   • 生成能力：生成依赖上下文的语言，例如句子结构需考虑前后符号的关联（如自然语言中的某些复杂结构）。
   • 自动机：线性有界非确定性图灵机（LBA）。
   • 规则特点：生产规则需保持符号数量非递减（如αAβ → αγβ，其中A为非终结符，γ非空）。

3. 类型2：上下文无关语法

   • 生成能力：适用于编程语言和自然语言中的嵌套结构（如括号匹配），但不能处理上下文依赖。
   • 自动机：下推自动机（PDA）。
   • 规则特点：规则形式为A → α，其中A为非终结符，α为任意符号组合（如A → aBc）。

4. 类型3：正则语法

   • 生成能力：描述简单模式（如标识符、数字），用于正则表达式和词法分析。
   • 自动机：有限自动机（FA）。
   • 规则特点：右线性（A → aB）或左线性（A → Ba）规则，仅允许单侧非终结符扩展。

层次结构的包含关系

• 每个层级的语言类严格包含于更高层级的语言类中，即：
  类型3 ⊂ 类型2 ⊂ 类型1 ⊂ 类型0。
  例如，正则语言（类型3）同时也是上下文无关语言（类型2），但反之不成立。