文章目录
一、自动机设计
二、自动机设计 1
三、自动机设计 2
四、自动机设计 3
五、自动机设计技巧
一、自动机设计
设计自动机 : 之前是根据给定的自动机 , 找到自动机所能识别的语言 ; 现在是 给定语言 , 设计出能识别该语言的自动机 ;
自动机设计需求 : 设计一个又穷自动机 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
设计 L = { w ∣ w 以 1 开 始 , 以 0 结 束 } \rm L = \{ w | w 以 1 开始 , 以 0 结束 \}L={w∣w以1开始,以0结束} 语言对应的 确定性有限自动机 ; 字母表为 { 0 , 1 } \rm \{ 0, 1 \}{0,1} ;
1 . 开始状态 : 首先要考虑 第一个状态 q 1 \rm q_1q
1
是 接受状态 还是非接受状态 ,
如果是 接受状态 , 使用双圈表示 ,
如果是 非接受状态 , 使用单圈表示 ;
第一个状态时 , 还没有读取字符 , 不符合 L \rm LL 语言要求 , 使用单圈表示 ;
2 . 开始状态 q 1 \rm q_1q
1
状态指令 : 读取的第一个字符必须是 1 11 , 读取 1 11 字符 后进入 q 2 \rm q_2q
2
状态 ;
如果读取 0 00 字符 , 则不符合 L \rm LL 语言要求 , 卡在开始状态 , 自动机停机 ;
3 . q 2 \rm q_2q
2
状态指令 : 可以读取 0 , 1 0, 10,1 字符 ,
读取 0 00 字符即进入 q 3 \rm q_3q
3
接受状态 ,
读取 1 11 字符后回到 q 2 \rm q_2q
2
非接受状态 ;
4 . q 3 \rm q_3q
3
状态指令 : 可以读取 0 , 1 0, 10,1 字符 ,
读取 0 00 字符还是进入本 q 3 \rm q_3q
3
接受状态 ,
读取 1 11 字符后回到 q 2 \rm q_2q
2
非接受状态 ;
自动机设计如下 :
三、自动机设计 2
设计 L = { w ∣ w 至 少 含 有 3 个 1 } \rm L = \{ w | w 至少含有 3 个 1 \}L={w∣w至少含有3个1} 语言对应的 确定性有限自动机 ; 字母表为 { 0 , 1 } \rm \{ 0, 1 \}{0,1} ;
1 . 开始状态 : 首先要考虑 第一个状态 q 1 \rm q_1q
1
是 接受状态 还是非接受状态 ,
如果是 接受状态 , 使用双圈表示 ,
如果是 非接受状态 , 使用单圈表示 ;
第一个状态时 , 还没有读取字符 , 肯定没有 3 33 个 1 11 , 不符合 L \rm LL 语言要求 , 使用单圈表示 ;
2 . 开始状态 q 1 \rm q_1q
1
状态指令 :
如果读取 0 00 字符 , 原地不动 , 保持 q 1 \rm q_1q
1
状态不变 ;
如果读取 1 11 字符 , 则跳转到 q 2 \rm q_2q
2
状态 ;
3 . q 2 \rm q_2q
2
状态指令 :
如果读取 0 00 字符 , 原地不动 , 保持 q 2 \rm q_2q
2
状态不变 ;
如果读取 1 11 字符 , 则跳转到 q 3 \rm q_3q
3
状态 ;
4 . q 3 \rm q_3q
3
状态指令 :
如果读取 0 00 字符 , 原地不动 , 保持 q 3 \rm q_3q
3
状态不变 ;
如果读取 1 11 字符 , 则跳转到 q 4 \rm q_4q
4
状态 ;
5 . q 4 \rm q_4q
4
状态指令 : 截止到此处 , 前面已经读取了 3 33 个 1 11 字符 , 达到接受状态标准 ;
自动机设计如下 :
四、自动机设计 3
设计 L = { w ∣ w 含 有 子 串 0101 } \rm L = \{ w | w 含有子串 0101 \}L={w∣w含有子串0101} 语言对应的 确定性有限自动机 ; 字母表为 { 0 , 1 } \rm \{ 0, 1 \}{0,1} ;
分析 : L \rm LL 语言中每个字符串的形式为 x 0101 y \rm x0101yx0101y , 其中 x , y \rm x, yx,y 可以是空字符 , 也可以是若干个字符 ;
1 . 开始状态 : 首先要考虑 第一个状态 q 1 \rm q_1q
1
是 接受状态 还是非接受状态 ,
如果是 接受状态 , 使用双圈表示 ,
如果是 非接受状态 , 使用单圈表示 ;
第一个状态时 , 还没有读取字符 , 肯定没有读取到 0101 01010101 子串 , 不符合 L \rm LL 语言要求 , 使用单圈表示 ;
起始状态 q 1 \rm q_1q
1
读取完第一个 子串 字符 0 00 后的状态 q 2 \rm q_2q
2
读取完第二个 子串 字符 1 11 后的状态 q 3 \rm q_3q
3
读取完第三个 子串 字符 0 00 后的状态 q 4 \rm q_4q
4
读取完第四个 子串 字符 1 11 后的状态 q 5 \rm q_5q
5
2 . 开始状态 q 1 \rm q_1q
1
状态指令 :
如果读取 1 11 字符 , 不符合子串起始字符 0 00 , 原地不动 , 保持 q 1 \rm q_1q
1
状态不变 ;
如果读取 0 00 字符 , 则跳转到 q 2 \rm q_2q
2
状态 ;
3 . q 2 \rm q_2q
2
状态指令 :
如果读取 0 00 字符 , 不符合子串第二个字符 1 11 , 但是这个字符有可能是 0101 01010101 子串第一个字符 , 保持 q 2 \rm q_2q
2
状态不变 , 将该子串当做第一个字符 ;
如果读取 1 11 字符 , 则跳转到 q 3 \rm q_3q
3
状态 ;
4 . q 3 \rm q_3q
3
状态指令 :
如果读取 1 11 字符 , 不符合子串第三个字符 0 00 , 直接跳转到起始状态 q 1 \rm q_1q
1
, 继续读取后续字符 ;
如果读取 0 00 字符 , 则跳转到 q 4 \rm q_4q
4
状态 ;
5 . q 4 \rm q_4q
4
状态指令 :
如果读取 0 00 字符 , 不符合子串第四个字符 1 11 , 可以当做第一个字符 , 这里跳转到 q 2 \rm q_2q
2
状态 ;
如果读取 1 11 字符 , 则跳转到 q 5 \rm q_5q
5
状态 ;
6. q 5 \rm q_5q
5
状态指令 : 此时已经读取完 0101 01010101 子串 , 达到接受状态 ; 不管后续读取什么字符 , 都保持不变即可 ;
如果读取 0 00 字符 , 保持本状态不变 ;
如果读取 1 11 字符 , 保持本状态不变 ;
自动机设计如下 : 下图中从左到右就是 q 1 , q 2 , q 3 , q 4 , q 5 \rm q_1 , q_2, q_3, q_4, q_5q
1
,q
2
,q
3
,q
4
,q
5
五个状态 ;
五、自动机设计技巧
可以先将主干设计出来 , 然后再考虑每个状态的其它分支字符 , 只要合理即可 ;
设计出的自动机可能不是最右的 ;
