《从语言到确定的有限自动机》由会员分享,可在线阅读,更多相关《从语言到确定的有限自动机(13页珍藏版)》请在金锄头文库上搜索。
1、1从语言到确定的有限自动机从语言到确定的有限自动机n n例:识别例:识别 = = 0,10,1上能被上能被5 5整除的二进制数整除的二进制数0123 开始4方法:方法:1 1、列出全部可能的状态、列出全部可能的状态2 2、从各个状态出发,构造边及输入字符记号、从各个状态出发,构造边及输入字符记号2n n例:识别例:识别 = = 0,10,1上能被能上能被能5 5整除的二进制数整除的二进制数0123 开始40从语言到确定的有从语言到确定的有 限限 自自 动动 机机3n n例:识别例:识别 = = 0,10,1上能被能上能被能5 5整除的二进制数整除的二进制数0123 开始410从语言到确定的有从
2、语言到确定的有 限限 自自 动动 机机4n n例:识别例:识别 = = 0,10,1上能被能上能被能5 5整除的二进制数整除的二进制数0123 开始4100从语言到确定的有从语言到确定的有 限限 自自 动动 机机5n n例:识别例:识别 = = 0,10,1上能被能上能被能5 5整除的二进制数整除的二进制数0123 开始41001从语言到确定的有从语言到确定的有 限限 自自 动动 机机6n n例:识别例:识别 = = 0,10,1上能被能上能被能5 5整除的二进制数整除的二进制数0123 开始410010从语言到确定的有从语言到确定的有 限限 自自 动动 机机7n n例:识别例:识别 = =
3、0,10,1上能被能上能被能5 5整除的二进制数整除的二进制数0123 开始4100101从语言到确定的有从语言到确定的有 限限 自自 动动 机机8n n例:识别例:识别 = = 0,10,1上能被能上能被能5 5整除的二进制数整除的二进制数0123 开始41001010从语言到确定的有从语言到确定的有 限限 自自 动动 机机9n n例:识别例:识别 = = 0,10,1上能被能上能被能5 5整除的二进制数整除的二进制数0123 开始410010101从语言到确定的有从语言到确定的有 限限 自自 动动 机机10n n例:识别例:识别 = = 0,10,1上能被能上能被能5 5整除的二进制数整除
4、的二进制数0123 开始4100101010从语言到确定的有从语言到确定的有 限限 自自 动动 机机11n n例:识别例:识别 = = 0,10,1上能被能上能被能5 5整除的二进制数整除的二进制数0123 开始41001010101从语言到确定的有从语言到确定的有 限限 自自 动动 机机12n n例:识别例:识别 = = 0,10,1上能被能上能被能5 5整除的二进制数整除的二进制数0123 开始41001010101从语言到确定的有从语言到确定的有 限限 自自 动动 机机13构造DFA,接受 0和1的个数都是偶数的字符串3120111 10000开始偶0偶1奇0奇1奇0偶1偶0奇1从语言到确定的有从语言到确定的有 限限 自自 动动 机机