A-A+

设DFA M=(Q ∑ f qo (qz}) 假设对任意a∈三 有f(qo a)=f(qz

2022-08-12 20:29:06 问答库 阅读 197 次

问题详情

设DFA M=(Q,∑,f,qo,(qz}),假设对任意a∈三,有f(qo,a)=f(qz,a)。证明:如果ω是L(M)中的非空串,则对所有k>0,ωk∈L(M)。


请帮忙给出正确答案和分析,谢谢!

参考答案

正确答案:证明:因为对任意a∈∑有f(q0a)=f(qza)所以对任意ω=ω1ω2…ωnωi∈∑n≥1有f(…f(f(q012)…ωn)=f(…f(f(qzω12)…ωn)。又若ω是L(M)中的非空串则有f(…f(f(q0ω12)…ωn)=qzf(…f(f(qzω12)…ωn)=qz即有f(q0ωk)=f(qzωk-1)=f(qzωk-2)=f…(qzω)=qz所以ω∈L(M)
证明:因为对任意a∈∑,有f(q0,a)=f(qz,a),所以对任意ω=ω1ω2…ωn,ωi∈∑,n≥1,有f(…f(f(q0,(ω1),ω2)…ωn)=f(…f(f(qz,ω1),ω2)…ωn)。又若ω是L(M)中的非空串,则有f(…f(f(q0,ω1),ω2)…ωn)=qz,f(…f(f(qz,ω1),ω2)…ωn)=qz即有f(q0,ωk)=f(qz,ωk-1)=f(qz,ωk-2)=f…(qz,ω)=qz所以ω∈L(M)

考点: