形式语言

维库，知识与思想的自由文库

形式语言是一个字母表上的某些有限长字串的集合。一个形式语言可以包含无限多个字串。

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

[编辑] 语言的形式定义

字母表 Σ 为任意有限集合，ε 表示空串， 记 Σ⁰ 为{ε}，全体长度为 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}

[编辑] 语言的表示方法

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

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

[编辑] 参见

• 计算机科学课程列表