Atitit 乔姆斯基分类 语言的分类 目录 1.1. 0 –递归可枚举语法 1 1.2. 1 –上下文相关的语法 自然语言 1 1.3. 2 –上下文无关的语法 gpl编程语言 1 1.4. 3

Atitit 乔姆斯基分类 语言的分类

目录

1.1. 0 –递归可枚举语法 1

1.2. 1 –上下文相关的语法 自然语言 1

1.3. 2 –上下文无关的语法  gpl编程语言 1

1.4. 3 –常规语法  正则表达式 1

2. 形式语言（英语：Formal language）是用精确的数学或机器可处理的公式定义的语言。 2

3. 常见形式语言 2

3.1. 例如数学家用的数字和运算符号 2

3.2. 、化学家用的分子式等。 2

3.3. 编程语言也是一种形式语言，是专门设计用来表达计算过程的形式语言。 [2] 2

3.4. 正则表达式 各种表达式 2

3.5. 各种 ql等 2

1. 1. 0 –递归可枚举语法

0类语法（无限制语法）包括所有形式语法。它们生成的图灵机完全可以识别所有语言。这些语言也称为递归枚举语言。请注意，这与递归语言不同，后者可以通过始终停止的图灵机来确定。

0级语法太笼统，无法描述编程语言和自然语言的语法。

1. 1. 1 –上下文相关的语法 自然语言

1. 1. 2 –上下文无关的语法  gpl编程语言

类型2语法生成上下文无关的语言。这些规则由A→γ形式的规则定义，其中A为非末端，而γ为末端和非末端的字符串。这些语言正是非确定性下推自动机可以识别的所有语言。上下文无关的语言是大多数编程语言语法的理论基础。

例：

A→aBc

1. 1. 3 –常规语法  正则表达式

Type-3语法生成常规语言。这样的语法将其规则限制在左侧的单个非终结符，以及由单个终结符组成的右侧，并且可能在单个非终结符之后（或在同一语法中但不是同时出现）。如果S未出现在任何规则的右侧，则此处也允许规则S→ε 。这些语言正是可以由有限状态自动机决定的所有语言。此外，可以通过常规表达式获得这套形式语言。常规语言通常用于定义搜索模式和编程语言的词汇结构。
例：

在数学、逻辑和计算机科学中，

1. 形式语言（英语：Formal language）是用精确的数学或机器可处理的公式定义的语言。

如语言学中语言一样，形式语言一般有两个方面：语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。

1. 常见形式语言
   1. 例如数学家用的数字和运算符号
   2. 、化学家用的分子式等。
   3. 编程语言也是一种形式语言，是专门设计用来表达计算过程的形式语言。 [2]
   4. 正则表达式 各种表达式 
   5. 各种 ql等

Atitit 语言分类 形式语言