形式语言

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

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

语言的形式定义

字母表与字符串

语言定义在某一个特定的字母表上，字母表（经常记作 Σ ）可以为任意有限集合。例如集合 $\{a,b,c...,z\}$ 就表示所有小写字母构成的字母表。

字符串是字母表中的元素构成的有穷序列，以之前定义的小写字母表为例，“hello”，“wikipedia”,“abcjkg”都是上面的串，而“AbCd”就不是上面的串了。记号 ε 表示空串——它是一个特殊的长度为0的串。

语言

直觉上，一个语言是字母表所能构成的所有串的集合的一个子集，具体来说：

对于任意一个字母表，记全体长度为 n 的子串为 $\Sigma ^{n}$ ，特别的，规定 $\Sigma ^{0}$ 为{ε}，则还可以定义

$\Sigma ^{*}=\Sigma ^{0}\cup \Sigma ^{1}\cup \cdots \cup \Sigma ^{n}\cup \cdots$

$\Sigma ^{*}$ 包含了字母表 $\Sigma$ 所能构成的所有字符串。语言（一般记为 L ）定义为 $\Sigma ^{*}$ 的任意子集。

下面给出一些语言的例子， $\{hello,world\}$ 是一个包含两个字符串的集合，也可以被视为小写字母构成的字母表上的一个语言。而实际上研究的语言的例子则常常更为复杂，例如所有合法的C语言程序串构成的集合也可以视作ASCII上的一个语言（假定编译器只支持英文符号）。

需要注意的一点是， $\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}

语言的表示方法

不像自然语言，一个形式语言作为一个集合，需要有某种明确的标准来定义一个字符串是否是它的元素。这可以通过多种方法来完成，下面将给出一些例子：

枚举法

如果一个形式语言的元素数目是有限的，那么可以通过枚举它的各个字符串来严格地定义它。

形式文法

通过形式文法来产生（参见乔姆斯基谱系）。

正则表达式

正则表达式是一种很多编程语言和库都支持的语法，这种语法可以用于匹配符合一定条件的字符串，经常用于文本的搜索和过滤。从名称上来说，正则表达式应当是对应于正则语言的，在形式语言领域内所称的正则表达式确实如此。不过，在实际的编程语言中，很多正则表达式已经通过引入复杂的扩展，可以匹配正则表达式所不能描述的内容。形式语言中的正则表达式和一般编程语言中所称的正则表达式在语法上也有较大差异。

自动机

直觉上来说，自动机消耗输入符号，并在自身的不同状态间转移，可以通过状态机消耗完整个字符串之后是否达到某些特定状态来定义一个字符串是否属于某一个语言。语言可以通过某种自动机来识别，比如图灵机、有限状态自动机。

参考文献

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

参见

外部链接