首页 > 试题广场 >

用Af对上述字符串进行分类的结果为?

[单选题]

已知有限状态自动机Af=(?，Q，d，q0，F)，?={0，1}；Q={q0，q1}；d：d(q0，0)= q1，d(q0，1)= q1，d(q1，0)=q0，d(q1，1)=q0；q0=q0；F={q0}。现有输入字符串：(a) 00011101011，(b) 1100110011，(c) 101100111000，(d)0010011，试问，用Af对上述字符串进行分类的结果为

```
ω1:{a,c};ω2:{b,d}
```
```
ω1:{a,d};ω2:{b,c}
```
```
ω1:{b,d};ω2:{a,c}
```
```
ω1:{a,b};ω2:{c,d}
```

查看答案及解析

kaiseu

？：代表输入的序列，这里输入可以是0或1；

Q：代表状态集合，这里可以是q0或者q1；

d：代表状态转换关系，d：d(q0，0)= q1，d(q0，1)= q1，表示在状态q0的时候输入0或者1都会转到状态q1；

q0：代表初始状态，就是说自动机在还未处理输入的时候的状态(明显的 q0∈ Q)；

F：代表终止状态，是 Q 中的状态的集合(就是 F⊆Q)。

所以，q0状态输入0或1都会转到q1状态，q1状态输入0或者1都会转到q0状态，也就是最终的状态决定与输入序列的长度。

发表于 2015-09-28 10:32:01 回复(2)

寒酸的教练

根据d中规则，状态q0时，接收输入0或者1都会转换到状态q1，而状态q1时，接收输入0或者1又都会转换到状态q0。
因此该状态机，就是判断输入字符串的长度，长度为偶数，则最终状态等同于初始状态q0，否则最终状态为q1。
a字符串长度为11，d字符串长度为7，两者最终状态都为q1；
b字符串长度为10，c字符串长度为12，两者最终状态都为q0。

发表于 2015-09-19 13:08:11 回复(2)