以下 NFA 中的 e-closure(r) 是什么

Question

对不起大家，我不能在这里提供图片...我无法上传图片...所以..我会给出问题的过渡 table。

(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} 的 e-closure 是否具有起始状态 {p}......，即使起始状态不会通过 elipson到最终状态 .....但是...最终状态通过 elipson 到达起始状态到状态 {q} 然后到达起始状态 {p}

在我的书中给出了

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

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

Answer 1

ϵ-closure(s) is a set of NFA states reachable from NFA state s on ϵ-transitions alone.

你的想法是对的。请按照上述定义。

因此，ε-闭包 (r) = 仅在 ε-转换上从 NFA 状态 r 可达的 NFA 状态集 = {p,q,r}。因此，您的书计算错误。

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

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