设计一个NFA，其中Σ = {0, 1}，并接受所有长度至少为2的字符串。

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

δ: Q X Σ -> 2Q

非确定有限自动机定义为一个五元组，

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

其中，

• Q: 有限状态集
• Σ: 有限的输入符号集
• q0: 初始状态
• F: 终结状态
• δ: 转移函数: Q X Σ -> 2Q

问题

为给定语言设计一个状态转换图和状态转换表，该语言接受所有长度至少为2的字符串。

解决方案

在继续解决方案之前，让我们了解一下字符串长度的含义以及如何查找任何字符串的长度。

**字符串长度**表示字符串或单词中符号的数量。它用|w|表示。

例如：w=01011001 来自二进制字母表Σ={0,1}

|w| = 8

在给定的问题中，字符串的长度至少应为2。也就是说，长度应为2或更大，但不能小于2，且字母表为Σ = {0, 1}。

语言L= { 00,01,10,11,001,110,101,111,000,1101,0010,…….}

状态转换图

给定语言的NFA状态转换图如下：

状态转换表

状态转换表如下：

解释

• **步骤1** - q0是初始状态，输入'0'时它转到状态q1，输入'1'时转到状态q1。
• **步骤2** - q1是中间状态，输入'0'和'1'时都转到状态q2。
• **步骤3** - q2是终结状态，它包含ε转移。

示例2

构造一个NFA，其中Σ = {0, 1}，它接受所有以01结尾的字符串。

在给定的问题中，语言接受所有以01结尾的字符串。

语言L= { 01,101,1101,001,11001,0101,11101,0001,1001,00101,…….}

状态转换图

状态转换图如下：

状态转换表

状态转换表如下：

解释

• **步骤1** - q0是初始状态，输入'0'时它转到多个状态q0和q1，输入'1'时它转到状态q0本身。
• **步骤2** - q1是中间状态，输入'1'时转到状态q2。
• **步骤3** - q2是终结状态，它包含ε转移。

Bhanu Priya

更新于: 2021年6月11日

18K+ 浏览量

开启你的职业生涯

通过完成课程获得认证

开始学习