一、 设计自动机 ( 语言要求 )
设计自动机 : 之前是根据给定的自动机 , 找到自动机所能识别的语言 ; 现在是 给定语言 , 设计出能识别该语言的自动机 ;
自动机设计需求 : 设计一个又穷自动机 M MM , 满足以下的给定的语言要求 ; 即语言已经存在 , 求自动机 ;
1 . 自动机语言字符集 : Σ = { 0 , 1 } \Sigma = \{0, 1\}Σ={0,1} , 字符集是 0 00 和 1 11 组成 , 该自动机语言由 0 , 1 0 , 10,1 组成 , 如 0101 01010101 , 100111 100111100111 等 ;
2 . 自动机语言描述 :
① 自动机语言集合 : 自动机 M MM 所能接受的字符串都放在集合 A AA 中 , 集合 A AA 就是该自动机语言 ;
② 自动机语言要求 : 自动机 M MM 的语言 A AA 集合 中的字符串中都有 奇数 个 1 11 ;
3 . 接受状态 与 非接受状态 : 根据上述自动机语言要求 , 定义接受状态和非接受状态 ;
① 接受状态 : 如果当前输入的字符串中 , 含有奇数个 1 11 那么当前状态是 接受状态 ;
② 非接受状态 : 如果当前输入字符串中 , 有偶数个 1 11 , 那么当前的状态就是 非接受状态 ;
二、 设计自动机 ( 1 ) 开始状态
Start 开始状态 , 自动机启动后 , 自动跳转到 第一个状态 S SS ;
三、 设计自动机 ( 2 ) 状态 S SS 状态类型确定
第一个状态首先要考虑该状态是 接受状态 还是非接受状态 , 如果是接受状态 , 使用双圈表示 , 如果是非接受状态 , 使用单圈表示 ;
先说结论 : 第一个状态 S SS 是 非接受状态 , 是一个单圈 , 原因如下 :
处于第一个状态时 , 还没有读取任何输入信息 , 当前读取 0 00 个字符 ;
此时有 0 00 个 1 11 , 0 00 是偶数 , 也就是当前输入有偶数个 1 11 , 显然不符合语言的要求 ② 必须包含奇数个 1 11 ;
如果当前的状态 , 不符合 自动机语言要求 , 那么需要将当前状态设置成非接受状态 ;
此时的 S SS 状态就属于此类情况 , 其不符合 A AA 语言要求 , 有偶数个 1 11 , 因此 S SS 状态是非接受状态 , 需要使用单圈表示该非接受状态 ;
当前自动机 M MM 设计 :
四、 设计自动机 ( 3 ) 状态 S SS 输入输出分析
处于 S SS 状态时 , 设计自动机的原则是 , 考虑输入任何指令 , 其状态改变 , 即输入 0 00 指令 , 状态如何改变 , 输入 1 11 指令 , 状态如何改变 ;
在第一个状态 S SS 基础上 , 如果输入字符 0 00 , 此时还是有 偶数 个 1 11 , 其要到达的状态还是非接受状态 , 这里将该状态 继续指向 它自己 ; 输入序列 0 00 ;
在第一个状态 S SS 基础上 , 如果输入字符 1 11 , 此时还是有 奇数 个 1 11 , 此时其要达到一个新的状态 T TT , 这个新状态 符合 A AA 语言要求 , 有奇数个 1 11 , 是可接受状态 , 使用双圈表示 ; 输入序列 1 11 ;
当前自动机 M MM 设计 :
S SS 状态已经分析完毕 , 下面开始讨论 T TT 状态的自动机后续设计 ;
五、 设计自动机 ( 4 ) 状态 T TT 输入输出分析
处于 T TT 状态时 , 设计自动机的原则是 , 考虑输入任何指令 , 其状态改变 , 即输入 0 00 指令 , 状态如何改变 , 输入 1 11 指令 , 状态如何改变 ;
T TT 状态下 , 如果输入 0 00 , 此时还是有 1 11 个 1 11 , 即奇数个 1 11 , 其状态还是可接受状态 , 继续指向该状态自己 T TT ; 输入序列 00 0000 ;
T TT 状态下 , 如果输入 1 11 , 此时输入中出现 2 22 个 1 11 , 输入了 偶数 个 1 11 , 其状态就是 非接受状态 , 需要 跳转到 非接受状态 S SS , 箭头从 T TT 指向 S SS ; 输入序列 01 0101 ;
当前自动机 M MM 设计 :
