形式语言

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

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

语言的形式定义 [编辑]

字母表 Σ 为任意有限集合，ε 表示空串，记 $\Sigma ^{0}$ 为{ε}，全体长度为 n 的字串为 $\Sigma ^{n}$ ， $\Sigma ^{*}$ 为 $\Sigma ^{0}\cup \Sigma ^{1}\cup \cdots \cup \Sigma ^{n}\cup \cdots$ ，语言 L 定义为 $\Sigma ^{*}$ 的任意子集。

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

语言间的运算 [编辑]

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

字符串集合的交并补等运算。
连接运算：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}

语言的表示方法 [编辑]

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

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

参见 [编辑]

參考文獻 [编辑]

A. G. Hamilton, Logic for Mathematicians, Cambridge University Press, 1978, ISBN 0-521-21838-1.
Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, ISBN 0-7204-2506-9.
Michael A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978.
John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-029880-X.
Grzegorz Rozenberg, Arto Salomaa, Handbook of Formal Languages: Volume I-III, Springer, 1997, ISBN 3-540-61486-9.
Patrick Suppes, Introduction to Logic, D. Van Nostrand, 1957, ISBN 0-442-08072-7.

外部链接 [编辑]

形式语言

目录

语言的形式定义 [编辑]

语言间的运算 [编辑]

语言的表示方法 [编辑]

参见 [编辑]

參考文獻 [编辑]

外部链接 [编辑]

导航菜单

个人工具

名字空间

不转换

变换

查看

操作

搜索

导航

帮助

工具

其他语言