形式语言

维基百科，自由的百科全书

在数学、逻辑和计算机科学中，形式语言是用精确的数学或机器可处理的公式定义的语言。

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

目录 1 语言的形式定义 2 语言间的运算 3 语言的表示方法 4 参见 5 外部链接

[编辑] 语言的形式定义

字母表 Σ 为任意有限集合，ε 表示空串， 记 Σ⁰ 为{ε}，全体长度为 n 的字串为 Σⁿ ， Σ^* 为 Σ⁰∪Σ¹∪…∪Σⁿ∪…， 语言 L 定义为 Σ^* 的任意子集。

注记：Σ^* 的空子集 ∅ 与 {ε} 是两个不同的语言。

[编辑] 语言间的运算

语言间的运算就是 Σ^*幂集上的运算。

• 字符串集合的交并补等运算。
• 连接运算：L₁L₂ = { xy | x 属于L₁并且 y 属于L₂ }。
• 幂运算：Lⁿ = L … L （共 n 个 L 连接在一起），L⁰ = {ε}。
• 闭包运算：L^* = L⁰∪L¹∪…∪Lⁿ∪…。
• 右商运算：L₁/L₂ = {x | 存在 y 属于L₂使得 xy 属于L₁}。
• 设 S ⊆ Σ^* 是一个语言，S 的补语言定义为集合 {ω | ω ∈ Σ^* 且 ω ∉ S}

[编辑] 语言的表示方法

一个形式语言可以通过多种方法来限定自身，比如：

• 枚举出各个字串（只适用于有限字串集合）。
• 通过形式文法来产生（参见乔姆斯基谱系）。
• 通过正则表达式来产生。
• 通过某种自动机来识别，比如图灵机、有限状态自动机。

[编辑] 参见

• 计算机科学课程列表
• 形式文法
• 形式方法
• 形式科学
• 形式系统
• 数学符号
• 编程语言

[编辑] 外部链接

• Formal Language Definitions website 1/24/04
• James Power, Notes on Formal Language Theory and Parsing, 29 November 2002.
• Alexandru Mateescu and Arto Salomaa, "Preface" in Vol.1, pp. v-viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp.1-39
• Sheng Yu, "Regular Languages", Chapter 2 in Vol. 1
• Jean-Michel Autebert, Jean Berstel, Luc Boasson, "Context-Free Languages and Push-Down Automata", Chapter 3 in Vol. 1
• Christian Choffrut and Juhani Karhumäki, "Combinatorics of Words", Chapter 6 in Vol. 1
• Tero Harju and Juhani Karhumäki, "Morphisms", Chapter 7 in Vol. 1, pp. 439 - 510
• Jean-Eric Pin, "Syntactic semigroups", Chapter 10 in Vol. 1, pp. 679-746
• M. Crochemore and C. Hancart, "Automata for matching patterns", Chapter 9 in Vol. 2
• Dora Giammarresi, Antonio Restivo, "Two-dimensional Languages", Chapter 4 in Vol. 3, pp. 215 - 267

自动机理论: 形式语言和形式文法
乔姆斯基层级	文法	语言	极小自动机
类型 0	无限制	递归可枚举	图灵机
n/a	(无公用名)	递归	判定器
类型 1	上下文有关	上下文有关	线性有界
n/a	附标	附标	嵌套堆栈
n/a	树-邻接	适度上下文有关	嵌入下推
类型 2	上下文无关	上下文无关	非确定下推
n/a	确定上下文无关	确定上下文无关	确定下推
类型 3	正则	正则	有限
每个语言或文法范畴都是其直接上面的范畴的真子集。