形式语言与自动机4教学讲解教案.pdf

《形式语言与自动机4教学讲解教案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、FL&A第四讲有限状态自动机FL&A有限状态自动机确定有限自动机非确定有限自动机确定与非确定有限自动机的等价性有限自动机的一个应用—文本搜索带-转移的非确定有限自动机（确定）有限自动机的最小化FL&A确定有限自动机有限自动机的五要素1有限状态集Startqq011有限输入符号集00转移函数0一个开始状态0q1q一个终态集合231FL&A确定有限自动机确定有限自动机的形式定义一个确定有限状态自动机DFA(deterministicfiniteautomata)是一个五元组A=(Q,,,q,F).0有限状态集有限输入

2、符号集转移函数:QQ一个开始状态q0Q一个终态集合FQFL&A确定有限自动机转移图表示的DFAQ={q,q,q,q}10123Startq01q1={0,1}00(q0,0)=q2,(q0,1)=q1(q,0)=q,(q,1)=q1310(q,0)=q,(q,1)=q202300(q3,0)=q1,(q3,1)=q2q1q23q01F={q,q}03FL&A确定有限自动机转移表表示的DFAQ={q,q,q,q}012301={0,1}q0q2q1(q0,0)=q2,(q0,1)=q1(

3、q,0)=q,(q,1)=qqqq1310130(q,0)=q,(q,1)=q2023q2q0q3(q3,0)=q1,(q3,1)=q2qqqq0312F={q,q}03FL&A确定有限自动机DFA如何接受输入符号串1100101Startq01q10000q1q231FL&A确定有限自动机DFA如何接受输入符号串1100101Startq01q10000q1q231FL&A确定有限自动机DFA如何接受输入符号串1100101Startq01q10000q1q231FL&A确定有限自动机DFA如何接受输入符号串1100101S

4、tartq01q10000q1q231FL&A确定有限自动机DFA如何接受输入符号串1100101Startq01q10000q1q231FL&A确定有限自动机DFA如何接受输入符号串1100101Startq01q10000q1q231FL&A确定有限自动机DFA如何接受输入符号串1100101Startqq0110000q1q231FL&A确定有限自动机DFA如何接受输入符号串100Startq01q10000q1q231FL&A确定有限自动机DFA如何接受输入符号串100Startq01q10000q1q231FL&A确定有限自动机

5、DFA如何接受输入符号串100Startq01q10000q1q231FL&A确定有限自动机DFA如何接受输入符号串110101Startq01q10000q1q231FL&A确定有限自动机DFA如何接受输入符号串110101Startq01q10000q1q231FL&A确定有限自动机DFA如何接受输入符号串110101Startq01q10000q1q231FL&A确定有限自动机DFA如何接受输入符号串110101Startq01q10000q1q231FL&A确定有限自动机DFA如何接受输入符号串110101Startq01q10

6、000q1q231FL&A确定有限自动机DFA如何接受输入符号串110101Startq01q10000q1q231FL&A确定有限自动机扩展转移函数适合于输入字符串设一个DFAA=(Q,,,q0,F):QQ扩充定义:Q*Q对任何qQ，定义：1(q,)=q2若w=xa,其中x*,a,则(q,w)=((q,x),a)FL&A确定有限自动机扩展转移函数适合于输入字符串1Startqq0110010qqq举例00021q1q23(q,)=qqqq001130(q,0)=(q,0)=

7、q002q2q0q3(q,00)=(q,0)=q020q3q1q2(q,001)=(q,1)=q001(q,0010)=(q,0)=q013FL&A确定有限自动机DFA的语言设一个DFAA=(Q,,,q0,F)定义A的语言：L(A)=ww*(q0,w)F设L是上的语言，如果存在一个DFAA=(Q,,,q0,F)，满足L=L(A)，则可以证明L是一个正规语言.FL&A确定有限自动机DFA的语言举例=0,1上的语言L=ww中0、1数目的奇偶性相同，则L是一个正规语言.可证L是如下DF

8、A的语言.1证明Startqq011留作思考题00(采用互归纳法,00参考Example2.4q1q23和