科探空谷
  • Home
  • zhimind home
  • Categories
  • Tags
  • Archives
  • 留学
    • 学校库
    • 专业库
    • 研究方向与招生
    • 工具
    • GPA计算器
    • 脑洞背单词
    • 脱口而出

自动机作业1-正则表达式

目录

  • 开篇语
  • 无耻的分界线
  • 转折
  • 万万没想到(其实不至于)
  • 结论
目录

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

开篇语¶

第二周的编程练习非常简单——前两轮开课时不知道是不是会难很多, 总之这次把代码框架都搭好了, 顺利的话, 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 非常容易错乱,而老师题目中的几个选项稍认真分析下,可以直接判断正误, 我之前是有多不认真呢。


Published

9月 8, 2014

Category

计算机科学

Tags

  • 计算机科学 1
  • 算法 6
  • 自动机 1

Stay in Touch

  • Powered by Pelican. Theme: Elegant by Talha Mansoor