为在Σ= {0，1}上定义的以下语言构造一个NFA。D= {0^n 10^m10^q |n，m，q∈N，q≡nm (mod 5)}
需要帮助解决以下问题：
为在Σ= {0，1}上定义的以下语言构造一个NFA。
D= {0^n 10^m10^q |n，m，q∈N，q≡nm (mod 5)}
我对如何在语言的Q部分中创建NFA分解感到困惑。
回答 1
Stack Overflow用户
发布于 2020-02-13 03:42:21
我们可以使用五种状态来记住n mod 5的值：
_______________0______________
/ \
| |
V |
----->q0--0-->q1--0-->q2--0-->q3--0-->q4现在我们需要阅读1：
_______________0______________
/ \
| |
V |
----->q0--0-->q1--0-->q2--0-->q3--0-->q4
| | | | |
1 1 1 1 1
| | | | |
V V V V V
q0' q1' q2' q3' q4'现在，我们可以分别查看每个案例。对于q0'，我们知道我们在第一部分中看到了许多0，它们与0mod 5相同。因此，nm =0 (mod 5)是已知的。我们可以接受任意数量的0，然后是1，如果没有进一步的输入，则接受:我们可以让q0‘这样做：
_0_
/ \
| |
\ /
----->q0'--1-->qA对于q1'，我们将有q= nm (Mod5)=m(Mod5)，因为在这种情况下n=1(Mod5)。我们可以通过记住到目前为止的m(Mod5)的当前值，然后在q中查找那么多的0来实现这一点。也就是说，q1‘可以替换为：
_______________0________________________
/ \
| |
V |
----->q1'--0-->q1''--0-->q1'''--0-->q1''''--0-->q1'''''
| | | | |
1 1 1 1 1
| | | | |
V V V V V
qA<--0--qA'<--0--qA''<--0--qA'''<--0--qA''''qA与我们之前介绍的接受状态是一样的。对于q2'，我们可以跟踪nm的当前值(mod 5)，它是2m (Mod5)：
_______________0________________________
/ \
| |
V |
----->q2'--0-->q2''--0-->q2'''--0-->q2''''--0-->q2'''''
| | | | |
1 1 1 1 1
| | | | |
V V V V V
qA qA'' qA'''' qA' qA'''状态qA'，qA''，qA‘和qA’与前面介绍的相同，但请注意现在的顺序不同:这反映了这样一个事实:2x0=0(和以前一样)，2x1=2(不是1)，2x2=4(不是2)，等等。
我们可以对q3‘和Q4’做同样的事情：
_______________0________________________
/ \
| |
V |
----->q3'--0-->q3''--0-->q3'''--0-->q3''''--0-->q3'''''
| | | | |
1 1 1 1 1
| | | | |
V V V V V
qA qA''' qA' qA'''' qA''
_______________0________________________
/ \
| |
V |
----->q4'--0-->q4''--0-->q4'''--0-->q4''''--0-->q4'''''
| | | | |
1 1 1 1 1
| | | | |
V V V V V
qA qA'''' qA''' qA'' qA'将所有这些不同的DFA放在一个巨大的DFA中，可以保证得到一个可以工作的DFA。是否有本质上类似的NFA，我不能肯定。此DFA具有以下状态：
- q0，q0'：2状态
- q1，q1'，….，Q1‘：6 states
- q2，q2'，….，Q2‘：6 states
- q3，q3'，….，Q3‘：6 states
- q4，q4'，….，Q4‘：6 states
- qA，qA'，….，qA‘：5个状态
这总共是32个州。如果你想尝试最小化，你也许可以把它们中的一些去掉。
https://stackoverflow.com/questions/60194278
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号