Loading... # Formal Languages vs. Regular Languages *Formal Languages* 中文叫做形式语言，而 *Regular Languages* 叫做正则语言。而这两个概念单靠其中文名来理解，是容易让人迷惑的，也就是不能顾名思义了。 --- 首先，这两者都需要给出一个**字母表**（英文：alphabet）$\sum$，也就是包含所有可能出现的字符的集合。字母表是由非空符号或字型组成的**有限集合**，也就是语言中出现的符号、字母（英文：letter，也就是单个字<sup>1</sup>）以及其它词元的集合。照习惯称这个集合为字母表，但是可能叫做字符表或是词汇表会更好一些。注意字母表是一个有限集合（英文：finite set）。 在这里再给出一些记号（notation）以及定义（definition）。 字母表所构成的所有单词（words）的集合记作$\sum^{*}$，可以读作字母表的**闭包**（名字怪怪的不是嘛，见下文）。将语言$A$记作$L(A)$，读作语言$A$。我们将空字符串记作 $\epsilon = \{“”\}$ <sup>2</sup>，读作epsilon，在非确定有限自动机（NFA）中起到了重要作用。 单词（word）是字母表中元素组成的的**有限序列**（要注意这里称之为序列而不是集合）。比如语言$X=\{0,1\}$中，$0$、$011$、$1111$等称为语言$X$的中单词。 而上面提到的闭包（英文：Kleene closure，克林闭包）笼统的定义就是**由零个、一个或多个（就是任意个）字母表中的元素互相连接所组成的集合**，记作$A^*=\cup_{i\ge 0}A^i$。这里的闭包应与*计算机科学（英文：computer science）*中的捕获自由变量的函数区分开来，两者没有什么联系。这里之所以叫做闭包，是因为在这个集合（也就是闭包运算所产生的字符串集合）上定义的运算（并、闭包运算，并运算也被称为连接运算）的运算结果也在这个集合中，也就说满足了封闭性（是不是想起了群公理）。这里给出语言$$A$$的闭包的更简单的定义： $$A^*=\epsilon|A|AA|AAA|...$$ --- 现在回归正题。 基于字母表$\sum$，所谓*形式语言*，就是由该字母表上单词（word）组成的集合。也有一个等价的定义——字母表$\sum$上的形式语言是字母表闭包$\sum^{*}$的一个子集（英文：subset）。 而*正则语言（regular language/rational language，也称为正规语言）*，是一种可以被*正则表达式（英文：regular expression）*所定义的*形式语言*，所以*正则语言*相当于*形式语言*的一类子集。 顺便，上面的提到的*正则表达式*由$\epsilon$、$\sigma\in \sum$、$(r_1)^*$、$(r_1+r_2)$、$(r_1 r_2)$（当且仅当$r_1$、$r_2$为正则表达式）组成。其中$\sigma\in\sum$就是每一个字母表中的元素，而最后三个则是正则表达式中定义的三种运算： 1. 闭包、迭代 上文已介绍。 $A^*=\cup_{i\ge 0}A^i$ 2. 串接、连接 注意这个操作是分前后的。 $AB=\{ab|a\in A\ and\ b\in B\}$ 3. 并 也就是集合中的并集 $A+B=\{s|s\in A\ or\ s\in B \}$ 这三种运算的运算优先级由高到低排列，也就是说闭包的优先级最高，并的优先级最低。 --- 注： 1. 语言学中的*字*是语意的基本单位，即语素；一个字可以拥有多个字形。 2. 有时也被记作$\lambda$。 参考资料： ```APA [1] Wikipedia contributors. (2021, January 3). Regular language. In *Wikipedia, The Free Encyclopedia*. Retrieved 17:50, March 30, 2021, from https://en.wikipedia.org/w/index.php?title=Regular_language&oldid=998010276 [2] Wikipedia contributors. (2021, March 28). Formal language. In Wikipedia, The Free Encyclopedia. Retrieved 17:53, March 30, 2021, from https://en.wikipedia.org/w/index.php?title=Formal_language&oldid=1014601092 [3] Hopcroft, J. E., & Ullman, J. D. (1979). Introduction to Automata Theory, Languages and Computation (Addison-Wesley series in computer science) (1st ed.). Addison-Wesley Publishing Company. [4] Formal language - Encyclopedia of Mathematics. (2019). Encyclopedia of Mathematics. https://encyclopediaofmath.org/index.php?title=Formal_language ``` 最后修改：2021 年 03 月 31 日 02 : 53 PM © 允许规范转载 赞赏 请我喝杯咖啡 ×Close 赞赏作者 扫一扫支付 支付宝支付 微信支付
