0

在此处输入图像描述 考虑 DFA:

δ(A,01) 等于多少? 选项:

A) {D}    
B) {C,D}      
C) {B,C,D}       
D) {A,B,C,D}

正确答案是选项 B),但我不明白如何。请有人向我解释解决它的步骤,以及一般来说,我们如何解决任何 DFA 和任何过渡的问题?

谢谢。

4

1 回答 1

2

B) 选项不是正确答案!对于这个转移图。

在转换图(TG)中,符号ε表示NULL-move ( ε-move)。TG 中有两个 NULL 动作。

One:       (A) --- `ε` ---->(B)  
Second:    (A) --- `ε` ---->(C) 

一种ε-move无需消耗任何符号即可更改状态的方法。在您的图表中来自A to BA to C

δ(A,01) 等于多少?

问题问“A如果输入是01”,则状态的路径是什么。(据我了解,因为只有一个最终状态)

01可以通过两种方式之一进行处理。

  • (A) -- ε --->(B) -- 0 --> (B) -- 1 --> (D)

  • (A) -- ε --->(C) -- 0 --> (B) -- 1 --> (D)

01此外,即使您不想达到最终状态 ,也没有其他方法可以处理字符串。

[答案]
所以有问题(或者你做了)。

您可以学习如何从转换图中删除 NULL-move。另外如何为 DFA 编写正则表达式

如果您从 TG 中删除 null-moves,您将获得三种接受方式01

TG

没有 NULL-MOVE 的等效转换图

请注意,Graph 中有三个起始状态。

三种方式:

{ABD}  
{CBD}  
{BBD}     

总之state-(B),必须要来。

还有,你Consider the DFA :写错了。TG 不是确定性的,因为存在不确定性移动 δ(A,ε) 并且下一个状态是 B 或 C。

于 2012-12-20T06:17:22.437 回答