finite-automata - 如何求解这个 DFA 的 δ(A,01)？

Question

考虑 DFA：

δ(A,01) 等于多少？ 选项：

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

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

谢谢。

Answer 1

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

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

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

一种ε-move无需消耗任何符号即可更改状态的方法。在您的图表中来自A to B或A 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。

没有 NULL-MOVE 的等效转换图

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

三种方式：

{ABD}  
{CBD}  
{BBD}     

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

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