A-A+
设NFA M＝(Q ∑ f qo {gf}) 该NFA的状态图中既没有进入qo的弧 也没有离
问题详情
设NFA M＝(Q，∑，f，qo，{gf})，该NFA的状态图中既没有进入qo的弧，也没有离开qf，的弧，描述M经过下列修改后所接受的语言。 (1)增加从qf到qo的￡转移。 (2)增加从qo到每个qo可达状态的ε转移。 (3)增加从每个能沿着某条路径到达qf，的状态到qf的ε转移。 (4)同时做(2)和(3)。
请帮忙给出正确答案和分析，谢谢！
参考答案
正确答案：假设原NFA所识别的语言为集合S。(1)S+(2){χ｜χ是y的后缀y∈S)(3){χ｜χ是y的前缀y∈S)(4){χ｜χ是y的子串y∈S)
增加从qf，到q0的ε转移，则对任何可以拆分为几个L(M)中符号串连接的符号串，均可以通过几次从q0到qf，再qf，到q0。的ε转移，最后使在DFA上的运算停留在qf。(2)增加从q0到每个q0可达状态的ε转移，则原先属于L(M)的符号串，其任何后缀都可通过从q0到某个q0可达状态的￡转移，再按照在原L(M)上运行后面部分的方式在新的DFA上运行，最后终止在终态。(3)、(4)分析同上。
