状态中的状态转移图该如何设计?

发表于 2010-7-23 14:38

在应用状态机时，如何设计状态转移图?请大侠们指点下。

发表于 2010-8-2 14:06

比如说检测信号1101001101,如果输入的信号是它则输出1否则输出0，这样的话状态转移图该怎么设计呢？
请大侠们多多指教.

欧阳青云 · 发表于 2010-8-2 14:13

先确定状态集，然后根据状态和输出函数（这些都是根据具体要求所得）画图或制表即可。最后可能还要进行适当的优化（就是状态集最简化）。至于如何落实到某种计算机语言所对应的程序，那是程序设计的事情。

发表于 2010-8-2 15:04

但状态集怎么确定呢？就说信号1101001101，我都不知道他有多少种状态。

发表于 2010-8-2 15:16

re 4L:

状态集怎么确定？无定则。如若只识别1101001101，最直接就是S0，S1，....，S10，再加个S-err。其中S0是初态，S10是末态（或成果态），S-err是出错态。最直接的未必是最简的，所以才会有优化。

发表于 2010-8-2 15:32

先谢谢了，不过你这样说我还是不知道怎么确定那些状态之间是怎么转移的，特别是进入出错态时。

发表于 2010-8-2 15:40

这个....，如下：

S0,1 -> S1
S0,0 -> S-err
S1,1 -> S2
S1,0 -> S-err
S2,0 -> S3
S2,1 -> S-err
....
S9,1 -> S10
S9,0 -> S-err

到了S10和S-err都将终结。

发表于 2010-8-2 15:45

关于此，LZ不妨可以推广到识别一般的定长字符串。看看状态图会大概是个什么模样。

发表于 2010-8-2 15:48

那如果进入S-err状态呢？出来往哪个状态跳，S0？而且有些状态可以重复利用，比如说信号信号1101001101中有两个1101可以重复利用,就是在这里不知所向

发表于 2010-8-2 15:56

本帖最后由 HWM 于 2010-8-2 16:56 编辑

进入S-err则必须进行出错处理，然后再进入S0。至于有重复码且重复数任意，如果是紧挨着的，可以用“循环”替代，这也是优化的一种，但这里不行。

登录 · 发表于 2010-8-2 16:28

下图这样有错吗？你觉得还能不能再优化呢？

发表于 2010-8-2 17:01

这图画得....

转移箭头线上的输入（0，1）不对。若仅识别1101001101，基本就这样了，无法进一步优化。

发表于 2010-8-2 17:13

呵呵，我平常很少画图，而且没什么艺术细胞，只有这种水平了，见笑了。
哪个状态到哪个状态的输入（0，1）不对？
不过想想那个出错状态或许可以省掉。我得好好想想怎么优化得简单点。

发表于 2010-8-2 17:21

具体在7L已经标出。如：S0到S1的转移输入为1，而S0到S-err的转移输入为0。S-err不可省略，没此状态无法区分出错和初始态。

发表于 2010-8-2 17:26

我知道了。我少了一根线。谢谢了哈。