形式语言

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

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

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

目录 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	正则	正则	有限
每个语言或文法范畴都是其直接上面的范畴的真子集。

查 • 論 • 編 • 歷 语义网
背景	知识  · World Wide Web  · Internet  · 数据库  · 语义网络  · 本体工程  · 本体
分主题	Linked Data  · 数据网  · Hyperdata  · Dereferenceable URIs  · 本体  · 规则库  · 数据空间
应用	语义维基页面语义维基并不存在，英语维基百科对应页面为Semantic wiki。 · 语义发布页面语义发布并不存在，英语维基百科对应页面为Semantic publishing。 · 语义搜索页面语义搜索并不存在，英语维基百科对应页面为Semantic search。 · 语义宣传页面语义宣传并不存在，英语维基百科对应页面为Semantic advertising。 · 语义推理程序页面语义推理程序并不存在，英语维基百科对应页面为Semantic reasoner。 · 语义匹配页面语义匹配并不存在，英语维基百科对应页面为Semantic matching。 · 语义映射程序页面语义映射程序并不存在，英语维基百科对应页面为Semantic mapper。 · 语义代理程序页面语义代理程序并不存在，英语维基百科对应页面为Semantic broker。 · 语义分析方法页面语义分析方法并不存在，英语维基百科对应页面为Semantic analytics。 · 面向语义服务型架构页面面向语义服务型架构并不存在，英语维基百科对应页面为Semantic service oriented architecture。
相关主题	Web 2.0  · Web 3.0  · Plain Old Semantic HTML  · 搜索引擎优化  · 开放数据库连接  · References  · 信息架构  · 知识管理  · 集体智能  · 主题图  · XML  · 描述逻辑
标准	语法及支持技术 : 资源描述框架 (Notation 3  · Turtle  · N-Triples)  · SPARQL  · URI  · HTTP  · XML 模式、本体和规则 : RDFS  · OWL  · 规则交换格式  · 语义网规则语言 语义标注 : RDFa  · eRDF  · GRDDL  · 微格式 公共词表 : FOAF  · SIOC  · Dublin Core  · SKOS
人物	Tim Berners-Lee  · James Hendler  · Ora Lassila  · Nigel Shadbolt  · Wendy Hall
关键的语义网组织	W3C  · WSRI  · MIT  · OpenLink软件  · Talis工作组  · ClearForest  · 南安普敦大学  · DERI