形式语言
在数学、逻辑和计算机科学中，形式语言（英语：Formal language）是用精确的数学或机器可处理的公式定义的语言。
如语言学中语言一样，形式语言一般有两个方面: 语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。
目录
1 语言的形式定义
1.1 字母表与字符串
1.2 语言
2 语言间的运算
3 语言的表示方法
3.1 枚举法
3.2 形式文法
3.3 正则表达式
3.4 自动机
4 參考文獻
5 参见
6 外部链接
语言的形式定义
字母表与字符串
语言定义在某一个特定的字母表上，字母表（经常记作 Σ ）可以为任意有限集合。例如集合a,b,c...,zdisplaystyle a,b,c...,z
字符串是字母表中的元素构成的有穷序列，以之前定义的小写字母表为例，“hello”，“wikipedia”,“abcjkg”都是上面的串，而“AbCd”就不是上面的串了。记号 ε 表示空串——它是一个特殊的长度为0的串。
语言
直觉上，一个语言是字母表所能构成的所有串的集合的一个子集，具体来说：
对于任意一个字母表，记全体长度为 n 的子串为Σndisplaystyle Sigma ^n
Σ∗=Σ0∪Σ1∪⋯∪Σn∪⋯displaystyle Sigma ^*=Sigma ^0cup Sigma ^1cup cdots cup Sigma ^ncup cdots
Σ∗displaystyle Sigma ^*
下面给出一些语言的例子，hello,worlddisplaystyle hello,world
需要注意的一点是，Σ∗displaystyle Sigma ^*
语言间的运算
语言间的运算就是 Σ*幂集上的运算。
- 字符串集合的交并补等运算。
连接运算：L1L2 = xy 。- 幂运算：Ln = L … L （共 n 个 L 连接在一起），L0 = ε。
闭包运算：L* = L0∪L1∪…∪Ln∪…。
右商运算：L1/L2 = 存在 y 属于L2使得 xy 属于L1。- 设 S ⊆ Σ* 是一个语言，S 的补语言定义为集合 ω ∈ Σ* 且 ω ∉ S
语言的表示方法
不像自然语言，一个形式语言作为一个集合，需要有某种明确的标准来定义一个字符串是否是它的元素。这可以通过多种方法来完成，下面将给出一些例子：
枚举法
如果一个形式语言的元素数目是有限的，那么可以通过枚举它的各个字串来严格地定义它。
形式文法
通过形式文法来产生（参见乔姆斯基谱系）。
正则表达式
正则表达式是一种很多编程语言和库都支持的语法，这种语法可以用于匹配符合一定条件的字符串，经常用于文本的搜索和过滤。从名称上来说，正则表达式应当是对应于正则语言的，在形式语言领域内所称的正则表达式确实如此。不过，在实际的编程语言中，很多正则表达式已经通过引入复杂的扩展，可以匹配正则表达式所不能描述的内容。形式语言中的正则表达式和一般编程语言中所称的正则表达式在语法上也有较大差异。
自动机
直觉上来说，自动机消耗输入符号，并在自身的不同状态间转移，可以通过状态机消耗完整个字符串之后是否达到某些特定状态来定义一个字符串是否属于某一个语言。语言可以通过某种自动机来识别，比如图灵机、有限状态自动机。
參考文獻
.mw-parser-output .refbeginfont-size:90%;margin-bottom:0.5em.mw-parser-output .refbegin-hanging-indents>ullist-style-type:none;margin-left:0.mw-parser-output .refbegin-hanging-indents>ul>li,.mw-parser-output .refbegin-hanging-indents>dl>ddmargin-left:0;padding-left:3.2em;text-indent:-3.2em;list-style:none.mw-parser-output .refbegin-100font-size:100%
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. 引文使用过时参数coauthors (帮助)
Rozenberg, Grzegorz; Arto Salomaa. Handbook of Formal Languages: Volume I-III. Springer. 1997. ISBN 3-540-61486-9. 引文使用过时参数coauthors (帮助)
Suppes, Patrick. Introduction to Logic. D. Van Nostrand. 1957. ISBN 0-442-08072-7.
参见
- 形式文法
- 形式方法
- 形式科学
- 形式系统
- 数学符号
- 编程语言
- 本体语言
外部链接
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
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||
|
