● 已知一不确定的有穷自动机(NFA)如下图所示,该自动机所识别的语言可以用正规式()表示。 ()A. (

Question

● 已知一不确定的有穷自动机（NFA）如下图所示，该自动机所识别的语言可以用正规式（）表示。（）A. (0|1)* B. (0*|1*)*001 C. (0*|1*)*0(0|1)* D. (0*|1*)0(01)*

Answer 1

正确答案：D
从状态S到状态3有三条路径：一是什么都不输入；二是由状态S什么都不输入到达状态1时，输入若干个0后，再到达状态3；三是S什么都不输入到达状态2时，输入若干个1后，再到达状态3，综合得到0*|1*)，状态3到状态4只能输入0，所以从状态S到状态4为（0*|1*)0，状态4到终态Z有两条路径：一是什么都不输入即可到达；二是在状态5时输入0到达状态6，状态6时输入1返回状态5，此过程可以循环多次，最后到达终态Z，综合这两条路径得到（01）*。所以，从转态S到达状态Z可以用正规式(0*|1*)0(01)*表示。