正规式 r=(0|10)* 的 NFA、DFA 和 MFA 构造

构造 NFA N：首先，根据正规式 r，我们可以画出以下的状态转移图：

其中，起始状态为 S，终止状态为 F。根据图中的状态转移，可以构造出 NFA N：

其中，状态 q0 为起始状态，状态 q3 为终止状态。对于状态 q0，它可以通过ε转移进入状态 q1 或者状态 q2；对于状态 q1，它可以通过读入 0 转移到状态 q2，通过读入 1 转移到状态 q3；对于状态 q2，它可以通过读入 1 转移到状态 q3；对于状态 q3，它没有任何出边，是终止状态。

将 NFA N 确定化，得到最简 DFA M：首先，我们需要对 NFA N 进行ε闭包的计算：

ε闭包(q0) = {q0, q1, q2} ε闭包(q1) = {q1} ε闭包(q2) = {q2} ε闭包(q3) = {q3}

然后，我们可以根据ε闭包构造出 DFA M：

其中，状态 {q0, q1, q2} 为起始状态，状态 {q3} 为终止状态。对于状态 {q0, q1, q2}，它可以通过读入 0 转移到状态 {q2}，通过读入 1 转移到状态 {q3}；对于状态 {q2}，它可以通过读入 1 转移到状态 {q3}；对于状态 {q3}，它没有任何出边，是终止状态。

将 DFA M 最小化，得到 MFA M`：根据 DFA M 的状态转移图，我们可以画出以下的等价类表：

其中，状态 {q0, q1, q2} 和状态 {q3} 是不可合并的等价类，因为它们分别对应着 NFA N 中的起始状态和终止状态。因此，我们只需要将状态 {q0, q1, q2} 和状态 {q3} 合并，得到最小化的 DFA M`：

其中，状态 {q0, q1, q2} 和状态 {q3} 合并为状态 A，是起始状态和终止状态。对于状态 A，它可以通过读入 0 或 1 转移到自身。因此，最小化的 DFA M` 只有一个状态，是一个 MFA。