形式语言与自动机4非确定性与NFA课件.ppt

1、UJS2/5/2023 2:10 PM1UJS2/5/2023 2:10 PM2UJS2/5/2023 2:10 PM3q40,1非确定型有穷自动机N1q1q2q310,0,11UJS2/5/2023 2:10 PM4UJS2/5/2023 2:10 PM5UJS2/5/2023 2:10 PM6UJS2/5/2023 2:10 PM7UJS2/5/2023 2:10 PM8q40,1非确定型有穷自动机N1q1q2q310,0,11UJS2/5/2023 2:10 PM9N1中输入010110输入0q1q1q2q3q1q3q1q4q4q4q2q3q1q2q3q1q4q4q3q1输入1输入0输入

2、1输入1输入0UJS2/5/2023 2:10 PM10UJS2/5/2023 2:10 PM11UJS2/5/2023 2:10 PM12UJS2/5/2023 2:10 PM13q40,1倒数第三个字符是1的NFA-N2q1q2q310,10,1UJS2/5/2023 2:10 PM14q1100倒数第三个字符是1的DFAq000q100q01000q111q001q101q0111101110101001UJS2/5/2023 2:10 PM15q40,1增加 后的N2q1q2q310,1,0,1,UJS2/5/2023 2:10 PM16的妙用N3q0q50q1q2q3q40000UJ

3、S2/5/2023 2:10 PM17UJS2/5/2023 2:10 PM18N4的功能q3bq1q2a,baaN4能识别，a,baba和baa,而不接受b,bb,babba。思考，如何将这个NFA转化为DFAUJS2/5/2023 2:10 PM19UJS2/5/2023 2:10 PM20UJS2/5/2023 2:10 PM21UJS2/5/2023 2:10 PM22说明：定义中=，P(Q)表示Q的幂集，是Q的所有子集组成的集合。UJS2/5/2023 2:10 PM23q40,1非确定型有穷自动机N1q1q2q310,0,11UJS2/5/2023 2:10 PM2401q1 q1 q1,q2q2 q3 q3 q3 q4 q4 q4 q4 UJS2/5/2023 2:10 PM25UJS2/5/2023 2:10 PM26UJS2/5/2023 2:10 PM27UJS2/5/2023 2:10 PM28