怎样设计一个NFA， 识别长度为2k而前半段与后半段不同的输入
对于DFA，很容易想象是不可能状态数小于2^k的。但是对于NFA，我们只需要在前半段记录其中一位：“第i位为0/1”，总共2k种可能，然后在后半段匹配第k+i位为1/0即可。这样的话可以构造状态数是O(k^2)个的NFA。(答完才发现是个好老的坟...)k=3的时候大概长这样： 【怎样设计一个NFA， 识别长度为2k而前半段与后半段不同的输入】 
■网友
a^k b^k这种Type3型的正则文法搞不出来吧....
■网友
基本思路：符合条件的语言符合这样的性质：第1位和最后一位不同，或者第二位和倒数第二位不同以此类推，所以对每种这样的情况分别建立两个路径，分别是第i位是1，第2k-i+1位是0；第i位是0，第2k-i+1是1。每条路径上没有环，只有对称的两个位置是相反的数，其余是0/1。NFA接收一个句子的条件是存在一条路径，符合“或”的含义。最后每条路径的长度是2k，一共有k*2条路径，总共需要2k*(2k-1)+2个状态。
推荐阅读
- 聪明人养花，这3种“花”怎样也要养一盆，每年能省不少医药费
- 同比■同比增长7.1%！2021年的第一个节你花了多少钱？
- “他是我第一个会说普通话的老师”：一对师生折射青海山村蝶变
- “厉行节约反对浪费”主题设计公益活动成果发布
- 有必要重新开个C店吗
- 互联网怎样解决“家政服务上门速度慢”的问题
- 趣头条|雪佛兰创界，外观设计大气，你会喜欢这款车吗？
- 环球车讯网|全新大众途观，外观的设计更加时尚，更加大气，“满满”的高级感
- 趣头条|日产奇骏，整体设计不错，你会喜欢吗
- 怎样看待从1月8号起，QQ钱包开始提现收费