设计一个在{0,1}字母表上的DFA，接受1的数量为奇数且0的数量为偶数的字符串。

确定性有限自动机 (DFA) 是一个 5 元组

M=(Q, Σ, δ,q0,F)

其中，

  • Q：称为状态的有限集合。
  • Σ：称为字母表的有限集合。
  • δ：Q × Σ → Q 是转移函数。
  • q0 ϵ Q 是起始状态或初始状态。
  • F：结束状态或接受状态。

问题

构造一个接受1的数量为奇数且0的数量为偶数的DFA机器。

解决方案

在字母表 Σ={0,1} 上为这两个条件分别设计两个机器。

  • DFA 仅接受奇数个 1。

  • DFA 仅接受偶数个 0。

这里，

s1 = 开始

s2=奇数个 1 或开始 11

s3= 开始 11 并被接受，并停留在那里

s4 = 接受偶数个 0，奇数个 1 以及 0 1 0

s5=偶数个 1，奇数个 0 以及 0 1

s6=奇数个 1 奇数个 0

s7= 奇数个 1 奇数个 0 开始 010

s8=偶数个 0 没有 1

s0= 奇数个 0 没有 1

更新于：2021年6月15日

4K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告