小女子在此向大家继续请教一题。这是05年软件评测师真题，是和编译原理有关的。可是本人没有学好这门课程。实在不会解，希望大家给予指导（望附上解题思路）。不胜感激！
某一确定性有限自动机(DFA)的状态转换图如下图所示,令d=0|1|2|…|9, 则以下字
符串中,不能被该DFA接受的是____(28)____,与该DFA等价的正规式是_(29)___.(其中,
ε表示空字符)
① 3857 ② 1.2E+5 ③ -123. ④ .576E10
0
4
1
5
23
6
d
d
E-
ddE·d-
dd
(28)A. ①,②,③ B .①,②,④ C. ②,③,④ D. ①,②,③,④
(29)A.(-d|d)d*E(-d|d)d*|(-d|d)*.d*(ε|E(-d|d)d*)
B.(-d|d)dd*(.|ε)d*|(ε|E(-d|d)d*)
C.(-|d)dd*E(-|d)d*|(-d|d)dd*.d*(ε|E(-|d)d*)
D.(-d|d)dd*E(-d|d)d*|(-d|d|)dd*.d*(ε|E(-dd*|dd*))

● 对于以下编号为①,②,③的正规式,正确的说法是___(30)___
① (aa*|ab)*b ② (a|b)*b ③ ((a|b)*|aa)*b
(30)A.正规式①,②等价 B.正规式①,③等价
C.正规式②,③等价 D.正规式①,②,③互不等价

正确答案应为：28B 29C 30D

没有具体的DFA,怎么知道状态的翻转呢 ?还是要附上状态图啊

状态转换图呢？ 好像排版有问题，看不出来

楼主学的好仔细，我当时就直接放弃了，乱填一个。sdlkfj1

还是看这个吧:)

sdlkfj5

最近很忙没有时间再看。打算有空回去好好翻下编译的书。然后把这题弄懂。题目本身存在问题。我有时间会在网上找下完整的题目。然后再把完整题目和我的解题思路附上。非常感谢各位的关心。小女子在此有礼了呵呵sdlkfj5

sdlkfj7
记得当年在学校开这门课的时候画了好多这种状态图的
毕业两年，全扔了
完全忘了是怎么回事
哎
还是得温故啊

我把状态图贴出来了

都忘了。。。。还要用这个啊？

呵呵，是啊
好像就是状态图的变化吧sdlkfj2
偶也学过，不过荒废了
sdlkfj1

引用:

原帖由 apron 于 2007-4-18 17:32 发表
sdlkfj7
记得当年在学校开这门课的时候画了好多这种状态图的
毕业两年，全扔了
完全忘了是怎么回事
哎
还是得温故啊

都是这样子的啦

讲一下28和30吧。29实在是想不出。
30以我个人的经验觉得三个都不等价，也想不出什么理由。呵呵！
28是可以这样看：
先看看-123.为什么可以。先来负号，-， 从0到4；再看1，可以从4到1，（d可以选择从0到9的数字）；再看2，可以在1上自循环一次，从1到1；再看3，还可以在1上循环一次；最后那个点，.，可以从1到5。5是终结点，所以这个值是可以接受的。
看看3875，3可以被接受，从0到1；8，7，5都可以接受，都在结点1上自循环，但问题是接受完毕后并没有到达终结点，所以是无法接受完成的。
其他两个选项可以自己试试，不是没有到达终结点，就是在中途就无法继续接受了。

[ 本帖最后由 Tender 于 2007-5-23 17:57 编辑 ]

提醒大家一下，软件评测师考试中也有大部分内容来自软件设计师教材，一定要结合看看。

考都考完了。。。。。。。

软件测评师具体考哪些内容啊?有些什么要求?能说说吗

不荒废  学习什么

sdlkfj3

加油。正在学习中

sdlkfj3