2021-04-11 子集构造法有效性证明

本文主要介绍一下编译原理中的子集构造法的数学依据。
龙书中并没有给出证明，我们在这里补上。
网上虽然有一些证明，但大多数不是很细，这里给出一个详细的证明

NFA的形式化定义如下：
$NFA=(K,\sigma,f,S,Z)$ 为一个5元组
其中 $K$ 是所有状态的集合， $\sigma$ 是符号集合，
$f$ 是一个映射: $f:K\times \sigma -> 2^K$ (其中 $2^K$ 表示 $K$ 的所有子集的集合,对于该映射的像为空集的情形，把对应原像从定义域中排除，从而使得该映射的定义域为 $K\times \sigma$ 的子集，这一点后文中保持一致并且不再说明)
$S$ 为初始状态集合 $S\subset K$
$Z$ 是终止状态集合 $Z\subset K$

DFA为NFA的特例，满足以下两个额外条件:
1, $S$ 只包含一个元素
2, $f$ 的任意象都最多只包含一个元素

以上形式化定义十分抽象，但其实NFA只不过表达了一个无重边的有向图, $K$ 对应图的节点， $\sigma$ 对应图的边上的符号，若 $f(k,c) = T$ 则表示， $k$ 到 $T$ 中每个元素都有一条有向边，且这些边上的符号为 $c$ , $S$ 和 $Z$ 仅仅是 $K$ 的特殊子集

子集构造法主要是把一个 $NFA$ 转化为一个 $DFA$ ，为了给出其形式化描述，我们先给出以下定义:
1，给定 $NFA=(K,\sigma,f,S,Z)$
给定任意子集 $L\subset K$ ,以及任意一个符号 $c\in \sigma$
令 $f(L,c):= \cup f(x,c) 任意x \in L$

待构建的DFA记为: $DFA = (K',\sigma',f',S',Z')$
则有 $K'\subset 2^K$ , $\sigma' = \sigma$ ,
$f' : K' \times \sigma' \rightarrow 2^{K'}$
注意，根据 $DFA$ 的定义，其象最多只能包含一个元素，对于只包含一个元素的集合，我们这个元素替代，而对于不包含任何元素的集合，我们可以把其原像从定义域中排除；则上式可以简写为:
$f' : K' \times \sigma' \rightarrow K'$ 但是这个映射的定义域并非 $K'\times \sigma'$ 而是其子集。

简单来说， $DFA$ 的状态是原始 $NFA$ 的状态集合，其映射 $f'$ 把某个状态 $s\in K'$ 和某个符号 $c\in \sigma'$ 映射为唯一的状态 $s'\in K'$ ，但是有些映射的像为空（这些映射的原像将被我们从定义域 $K'\times \sigma'$ 中排除）

有了以上铺垫，我们用伪代码的形式，形式化的描述子集构造法:

0,初始5元组中所有集合为空集, $f'$ 的定义域为空集
1取定 $s' = S$ 并将其添加到 $K',S'$ ,并令 $s'$ 为未标定态
2，
$\quad while($ K' $中存在未标定的元素$ s $)\{$
$\quad \quad$ 标定 $s$
$\quad \quad$ $for( c: \sigma) \{$
$\quad \quad$ $t = f(s,c)$ （若(s,c)不在定义域，则continue）
$\quad \quad$ $if(t\notin K') t\rightarrow K'$ (箭头这里表示添加的意思，同时令该t为未标定态)
$\quad \quad$ 在 $f'$ 的定义域中添加 $(s,c)$ ,并令 $f'(s,c)=t$
$\quad\quad \}$
$\quad \}$

以上算法确定了除了 $Z'$ 之外的所有元素，之后我们把 $K'$ 中所有包含位于 $Z$ 中元素的的对象取出组成一个集合，设为 $Z'$

至此我们按照算法完全构建了 $DFA$

下面我们来做最关键的一步，证明以下两点:
1，子集构造法生成的图确实满足 $DFA$ 应该满足的性质
2, 该DFA和原始NFA表达相同的语言

证明：
1, $DFA$ 应该满足的性质为:
1-1, $S'$ 只包含一个元素
1-2, $f'$ 的任意象都最多只包含一个元素
根据我们的构建算法， $S'$ 中只包含 $s'$ ，因此1成立，且由于 $f$ 是单值映射，显然2成立

2，该DFA和原始NFA表达相同的语言
2-1
首先证明原始NFA的语言包含于DFA
我们把形如:
$a_1\in f(a_0,e_0), a_2\in f(a_1,e_1),.., a_n\in f(a_{n-1},e_{n-1})$
的关系简称为“包含链”,当 $a_0\in S$ 时，
对于NFA表达的语言中的任意一条语句， $e_0e_1...e_{n-1}$ ，显然必然存在满足上述条件的包含链

对于这样一条语句，我们考虑DFA构造方法,

有 $a_0\in S \in S'$
$S$ 会被执行一次标定，之后对于符号 $e_0$ ，将执行
$t= f(S,e_0)=\cup f(x,e_0) 任意x\in S$ 以及 $t->K'$
由 $a_1\in f(a_0,e_0)$ , $a_0\in S$ , 推出 $a_1\in t$
并且将有: $f'(S,e_0)= t$ 我们设 $S_1= t$ ；

则 $S_1$ 会被执行一次标定，之后对于符号 $e_1$ 将执行
$u =f(S_1,e_1)=\cup f(x,e_1)$ 任意 $x\in S_1$ 以及 $u->K'$
由 $a_2\in f(a_1,e_1),a_1\in S_1$ ,推出 $a_2\in u$
并且将有: $f'(S_1,e_1) = u$ 令 $S_2=u$ ;

.......，最终得到:
$f'(S,e_0)=S_1 ,f'(S_1,e_1)=S_2,... f'(S_{n-1},e_{n-1})=S_n$
而这等价于是说: $e_0e_1...e_{n-1}$ 属于该DFA的语言。

从最初选择 $NFA$ 的语句的任意性，证明完毕

2-2 其次证明DFA的语言不会超过NFA的语言，
DFA表达的语言中任意语句: $e_0e_1,...e_{n-1}$ 根据DFA映射特性，存在唯一的 $T_0,T_1,...T_n$ 满足以下条件：
1) $T_0=S$

$T_1 = f'(T_0,e_0) ,T_2=f'(T_1,e_1),...T_n=f'(T_{n-1},e_{n-1})$
我们考虑其中任意一个片段:
$T_i = f'(T_{i-1},e_{i-1}) , T_{i+1}=f'(T_{i},e_{i})$
根据 $DFA$ 构造算法，
$T_i = f'(T_{i-1},e_{i-1}) = f(T_{i-1},e_{i-1}) =\cup f(x,e_{i-1}) 任意x \in T_{i-1}$
将被执行一次，之后 $Ti$ 不会再被修改
这意味着 $Ti$ 中任意元素 $y$ 都，存在 $T_{i-1}$ 中至少一个元素 $x$ 使得 $y=f(x,e_{i-1})$

利用这个关系，我们不难推导出，存在元素:
$x_0\in T_0,x_1\in T_1,...x_n\in T_{n}$ 满足 $f(x_0,e_0)=x_1,f(x_1,e_1)=x_2,...f(x_{n-1},e_{n-1})=x_{n}$
结合 $x_0\in S$
这对应着NFA中的一条语句
证明完毕

最后编辑于：2021.04.12 16:35:02

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,294评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,493评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,790评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,595评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,718评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,906评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,053评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,797评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,250评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,570评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,711评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,388评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,018评论 3赞 316
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,796评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,023评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,461评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,595评论 2赞 350

2021-04-11 子集构造法有效性证明

推荐阅读更多精彩内容