考虑 DFA:
δ(A,01) 等于多少? 选项:
A) {D}
B) {C,D}
C) {B,C,D}
D) {A,B,C,D}
正确答案是选项 B),但我不明白如何。请有人向我解释解决它的步骤,以及一般来说,我们如何解决任何 DFA 和任何过渡的问题?
谢谢。
考虑 DFA:
δ(A,01) 等于多少? 选项:
A) {D}
B) {C,D}
C) {B,C,D}
D) {A,B,C,D}
正确答案是选项 B),但我不明白如何。请有人向我解释解决它的步骤,以及一般来说,我们如何解决任何 DFA 和任何过渡的问题?
谢谢。
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。