编程容易，笔算不易，且写且珍惜

开篇语¶

第二周的编程练习非常简单——前两轮开课时不知道是不是会难很多， 总之这次把代码框架都搭好了， 顺利的话， 10分钟就OK了。

不顺利的地方在哪儿——我使用的是python版本， 里面有个小bug，我看不懂输出。 在源文件里找了半天代码结构没明白， 最后打算从main开始吧， 一看， 代码里面是这样写的

def main(filepath):
     return Start('testRE.in')
if __name__ == '__main__':
     main(sys.argv[1])

好吧，难怪我的文件名参数没用——剩下的在看懂他输出是什么内容后很快就解决了。

无耻的分界线¶

你以为我就想说这个？ NO！ 最起码笔算不易还没说呢！！！

本周第一个视频讲的是正则表达式基础，从定义到正则表达式转换成NFA

CUT！！！

概念没兴趣， RE转NFA 学过的内容，看到那张图就OK了， 主要是确实so easy.

CONTINUE！！！

然后就到DFA转RE了， 说实话吧， 过程不是很复杂，对于我这种人来说，就一个公式（虽然后面不停地修正自己对过程理解上的缺陷）， 套公式，谁不会呢？！

转折¶

我还真不会了， 小测第一题就是DFA转RE, 4个状态之间的转换，

套用公式简单

$$ R^k_{ij} =R^{k-1}{ij} + R^{k-1}(R^{k-1}{kk})* R^{k-1} $$

问题有几个： 1. 状态的序号， 给状态按什么顺序分配序号最好呢，在这里可能没影响，不过我换了好几次。 2. 手算真是很绕， 整个下午，多半时间都花在推导上了，连午觉都想想后起来先推导了几次，实在绕晕了才午休。

在纸上推导被绕的过程中， 顺手写代码，模拟一下这个公式， 就是个递归的公式，用nnn 的数组来记录状态嘛。

初始版的数组下标就不对，不经过额外状态的路径（直接连结或无连结）被我忽略了， 另外也没有组织好正则表达式的表达形式，括号没用好。 输出的结果自然是无效的。

最后第二周的第一个小测是我经过7次连蒙带猜后，总算拿到5分。 第一题纸算太难，第二题花费很长时间来理解题意，后3题时不时拖后腿，几次前两题答对（后几次已经不是猜了），后三题不小心出错。

万万没想到（其实不至于）¶

到晚上， 做其他事耐心缺失之下， 又打开了代码， 决定调整好数组下标， 再组织好括号的输出。很快修改完毕， 随意运行之后，输出结果居然就这么达到预期 因 honor code， 只摘取与题目要求无关的输出部分

k i j regular expression
4 1 1 1(11+0(01+10))*(1+00)
4 1 2 1(11+0(01+10))*01
4 1 3 1(11+0(01+10))*0
4 1 4 1+1(11+0(01+10))*(11+0(01+10))
4 2 1 0(11+0(01+10))*(1+00)
4 2 2 0(11+0(01+10))*01
4 2 3 0(11+0(01+10))*0
4 2 4 0+0(11+0(01+10))*(11+0(01+10))
4 3 1 0+(01+10)(11+0(01+10))*(1+00)
4 3 2 1+(01+10)(11+0(01+10))*01
4 3 3 (01+10)(11+0(01+10))*0

虽然没有经过完全化简——也不确认全部正确，但形式上是没问题了。 测验第一题对应的结果也是正确的。

根据输出的结果， 回顾题目， 我去， 选项怎么这么明显啊， 我之前的推导都在为了什么？

结论¶

个人经验， 手工推导DFA到RE 非常容易错乱，而老师题目中的几个选项稍认真分析下，可以直接判断正误， 我之前是有多不认真呢。