closures - 遵循 NFA 的 e-closure(r) 将是什么

Question

对不起，我不能在这里提供图片...我无法上传图片...所以..我将给出问题的转换表。

(S/I)....a...b.....c.......e(elipson) 


p>.......{p}.....{q}...{r} ..¤(phi) 


q>.......{q} ....{r} ..¤.... {p} 


r(final)>..{r}...¤....{p}....{q} 

这里 ¤ 是 phai
p 是开始状态
r 是最终状态

我的疑问是......最终状态的电子关闭{r}是否有开始状态{p}......，即使开始状态不会直接到达elipson最终状态......但是......最终状态达到起始状态elipson到状态{q}，然后到起始状态{p}

在我的书中给出的是

e-closure (r)={r,q} 

但我的问题是为什么它不是 ....{p,q,r}...而最终状态{r}也达到了起始状态{p}...

Answer 1

ϵ-closure(s) 是一组 NFA 状态，仅在 ϵ-transitions 上可以从 NFA 状态 s 到达。

你的想法是正确的。请遵循上述定义。

因此，ϵ-closure(r) = NFA 状态集可从 NFA 状态 r 仅在 ϵ-transitions = {p,q,r} 上到达。因此，您的书计算错误。

答案必须是 {p,q,r}。

请注意，包含状态 {r} 是因为状态将始终在 ε-transition 时保留在其自身上。状态 {p} 是可能的，因为 p 可以从 NFA 状态 q 在 ϵ-transition 上到达，而 p 可以从 NFA 状态 r 在 ϵ-transition 上到达。