构造一个NFA，接受包含偶数个0或奇数个1的字符串。

非确定有限自动机 (NFA) 也具有与 DFA 相同的五个状态，但具有不同的转移函数，如下所示：

δ: Q X Σ → 2Q

其中，

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

问题

在字母表 Σ={0,1} 上构造 NFA。

解决方案

为这两个条件设计两个独立的机器，如下所示：

  • 仅接受奇数个1的NFA

  • 仅接受偶数个0的NFA

在字母表 Σ= {0,1} 上仅接受奇数个1的NFA。

它生成的语言是：

L={1,111,01,001,0111,0010,01110,…}

  • 状态 o1 在 0 上转到 o1，在 1 上转到状态 o2。

  • 状态 o2 在 0 上转到 o2，在 1 上转到 o1。

在字母表 Σ= {0,1} 上仅接受偶数个0的NFA

它生成的语言是：

L={100,1100,1010,1100010,……}

  • 状态 E1 在 1 上转到 E1，在 0 上转到 E2。

  • 状态 E2 仅在 1 上转到 E2，在 0 上转到 E1。

现在使用 epsilon 移动合并这两个转移图。

**接受所有包含偶数个0或奇数个1的字符串的NFA** 如下所示：

更新于： 2021年6月15日

11K+ 浏览量

开启您的职业生涯

通过完成课程获得认证

开始学习
广告