Formal Languages vs. Regular Languages
Formal Languages 中文叫做形式语言，而 Regular Languages 叫做正则语言。而这两个概念单靠其中文名来理解，是容易让人迷惑的，也就是不能顾名思义了。
首先，这两者都需要给出一个字母表（英文：alphabet）$\sum$，也就是包含所有可能出现的字符的集合。字母表是由非空符号或字型组成的有限集合，也就是语言中出现的符号、字母（英文：letter，也就是单个字1）以及其它词元的集合。照习惯称这个集合为字母表，但是可能叫做字符表或是词汇表会更好一些。注意字母表是一个有限集合（英文：finite set）。
在这里再给出一些记号（notation）以及定义（definition）。
字母表所构成的所有单词（words）的集合记作$\sum^{*}$，可以读作字母表的闭包（名字怪怪的不是嘛，见下文）。将语言$A$记作$L(A)$，读作语言$$A$$。我们将空字符串记作$\epsilon = {“”}$2，读作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$就是每一个字母表中的元素，而最后三个则是正则表达式中定义的三种运算：
-
闭包、迭代
上文已介绍。
$$A^*=\cup_{i\ge 0}A^i$$
-
串接、连接
注意这个操作是分前后的。
$AB={ab|a\in A\ and\ b\in B}$
-
并
也就是集合中的并集
$$A+B={s|s\in A\ or\ s\in B }$$
这三种运算的运算优先级由高到低排列，也就是说闭包的优先级最高，并的优先级最低。
注：
- 语言学中的字是语意的基本单位，即语素；一个字可以拥有多个字形。
- 有时也被记作$\lambda$。
参考资料：
1 | [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 |