形式语言

形式语言（正體）

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

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

目录

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}

语言的表示方法

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

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

参见

外部链接

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

2个分类: 形式语言 | 编译原理

Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History