MIEC-NOTE

Appearance

L1. 数学初步与有限状态机 Math Preliminaries & Finate State Automata ​

数学初步（有些内容 CS172 学过了） ​

集合 sets ​

通常：小写字母代表元素，大写字母代表集合

，，，，分别表示自然数集、整数集、有理数集、实数集

这里（包括 Sipser 的教材）认为自然数集 是不包含 的

表示无理数集， 表示复数集

集合运算 ​

  • 并集，
  • 交集，
  • 取反，
  • 减法，
  • 德摩根律
  • 分配律
  • 笛卡尔积，，也叫做叉积

函数 functions ​

函数是两个集合之间的二元关系。第一个集合当中的每个元素，最多与第二个集合当中的一个.有关（映射到）。

从集合 到集合 的函数 ，说白了就是定义域 而值域是 ，可以表示为 ，而这个函数是两个集合的笛卡尔积的子集，即：

若 则 ，vice versa。

字符串 strings ​

字符串基础知识 ​

  • 字母表（alphabet）：任意的非空有限集。通常用 表示
  • 字母表当中的元素，称之为字母表的 符号（symbols）
  • 字母表上的字符串（a string over an alphabet）是该字母表上的符号的有穷序列，且不含逗号、空格等分隔符
  • 字符串的集合，称为 语言（language）
  • 字符串 的长度表示为 ，长度为零的是空串，常用 表示
  • 若字母表 上的字符串 的长度为 ，则可以写作 ，翻转
  • 原始串当中连续（consecutively）出现的一段字符，是子串（substring）

连接（concatenation） ​

  • 假设 串的长度是 ， 串的长度是 ，则 和 的连接记作 ，

  • 表示 个 依次连接，即：，

字符串的偏序 ​

  • 若 是三个字符串且 ，则 是 的 前缀（prefix），满足 。

  • 特殊的，若 ，则 是 的 真前缀（proper prefix），此时满足 。

  • 如果在一个语言中，任何一个成员都不是其他成员的真前缀，则这个语言是前缀无关的 （无前缀的）（prefix-free）

语言连接 ​

与字符串的连接类似：

  • 若 和 是两个 语言（language），则定义 ，也可写作

  • ，。

克莱尼星号 Kleene Star ​

  • 这个星号是一种正则运算（连接）。 可以读作「A-Star」。
  • 若 是一个语言，则定义 （Sipser 的教材写作 ），表示 中任意个字符串连接形成的新串们构成的新语言。所以， 也是 的成员。
  • 当中有 个字符串。
  • 除了 ，还有一种东西叫做 ，说白了就是把 从 当中删掉。这两种表示和正则表达式当中一致。
  • 字母表 上的语言（language over an alphabet），都是 的子集。

有穷自动机和正则 ​

有穷自动机是描述能力和资源 极其有限 的计算机的 模型，经常被用作各种机电设备的控制器，如自动门等。

马尔科夫链（Markov chain）是一种概率的计算模型，是有限自动机的概率对应物。常用于识别数据中的模式，甚至用于预测金融市场的价格变化。

定义 ​

一个有穷自动机 是一个五元组 ：

  • 是有限的状态集
  • 是有限的字母表符号的集合
  • 是转换函数，
  • 是初始状态（state）
  • 是有限的接受态的集合（states）

若有一个有穷自动机 接受的全部字符串，构成集合 ，即 是 接受的全部字符串集合，则称：

  • 是 的语言（ is the language of ）
  • 识别 （接受了语言当中的所有字符串，即识别该语言）

因此，一个自动机可以接受许多字符串，但永远只能 识别（recognize） 一个语言。

正则语言 ​

正则（regular） 语言是指，存在某个有穷状态机，可以识别它。

例子：字母表 上有三个语言 ，

  • 语言 A：包含子串 11（正则）

  • 语言 B：1 的个数是偶数（正则）

  • 语言 C：0 与 1 的数量相等（非正则）（上下文无关）

正则运算 ​

设 和 是两个语言，则定义以下三个正则运算：

  • 并（union）：
  • 连接（concatenation）：
  • 星号（star）：

正则表达式就是由以上三种正则运算和 （atomic）构建出来的。（这条表述可能不太严谨，理解意思就好）

封闭性（closure） ​

正则语言类在三种正则运算下封闭。

正则语言类在 union 运算下封闭 ​

若 都是正则语言，则 也是正则语言。

证明：

若自动机 分别识别 ，则构造 ，把 和 的所有状态做笛卡尔积（相当于同时记录两边的路径）扔给 即可。即：

  • ，意思是第一个的接受态配上第二个的任意状态，并起来第二个的接受态配第一个的任意状态。这个表达式也可以改写为
  • 注意 ，这种表示方法是交集，因为 pair 中的两个元素必须分别在 当中，才能积进 。
  • 的写法也不准确。因为直接并起来，元素都是单独的，没有 pair 到一起。

总而言之，就是升高了一维，变成了二维。

图示见 Slide 2 的第 10 页。

对应的 NFA：

image-20220915230346059

正则语言类在 concatenate 运算下封闭 ​

若 都是正则语言，则 也是正则语言。

证明：

若 NFA 分别识别 ，则构造 ，把 的接受态连边到 的初始状态即可，边权是 。然后把原先的接受态改为普通状态。

图示见 slide1 的第 38 页（Slide 2 的第 11 页）

对应的 NFA：

image-20221124195046035

正则语言类在 star 运算下封闭 ​

若 是正则语言，则 也是正则语言。

对应的 NFA：（注意空的时候也可以接受）

image-20220915230354918