验证匹配以0首尾且含偶数个1的二进制串的正则表达式正确性
2026-8-13
正则表达式验证与修正
你给出的正则表达式0*, (1, 0*, 1)*, 0*不符合题目要求，主要问题有三点：
- 正则语法中用无符号连接表示连续匹配，逗号不是标准连接符，属于语法错误；
- 原表达式允许匹配空串（
0*可以匹配空），但题目要求单词必须以0开头和结尾，空串不满足； - 原表达式能匹配以1开头或结尾的串（比如
101会被(10*1)*匹配），违反首尾为0的规则。
符合要求的正则表达式应为：0(0*10*10*)*0
表达式拆解：
- 强制以
0开头和结尾，直接满足首尾要求； - 中间的
(0*10*10*)*用于保证包含偶数个1：每一对1可被任意数量的0包围，整体可重复0次（对应全0串，0个1是偶数）或多次； - 允许任意数量的0穿插在1之间，覆盖所有符合条件的二进制串。
子集闭包法将NFA转换为DFA
先基于修正后的正则表达式构造NFA，再通过子集闭包法生成DFA：
步骤1：构造对应NFA
将正则表达式拆解为子结构，设计NFA状态（S=初始状态，F=接受状态）：
- S →0→ A：初始状态读入0进入状态A
- A ε→ B：通过空转换进入中间循环起始状态B
- B →0→ B：状态B读入任意数量0仍停留在B
- B →1→ C：状态B读入1进入状态C
- C →0→ C：状态C读入任意数量0仍停留在C
- C →1→ B：状态C读入1回到状态B（完成一对1的匹配，保证偶数计数）
- B ε→ D：循环结束后通过空转换进入状态D
- D →0→ F：状态D读入0进入接受状态F
步骤2：计算ε-闭包
ε-闭包指从某状态出发，通过任意次空转换能到达的所有状态集合：
- EC(S) = {S}
- EC(A) = {A, B, D}（A→ε→B，B→ε→D）
- EC(B) = {B, D}（B→ε→D）
- EC(C) = {C}
- EC(D) = {D}
- EC(F) = {F}
步骤3：生成DFA状态与转移
DFA的状态是NFA的状态子集，初始状态为EC(S)={S}，逐状态计算读0/1后的转移：
| 当前DFA状态 | 读0后的ε-闭包（转移目标） | 读1后的ε-闭包（转移目标） | 是否为接受状态 |
|---|---|---|---|
| {S} | {A,B,D} | ∅ | 否 |
| {A,B,D} | {A,B,D,F}（A读0→A，B读0→B，D读0→F，取三者ε-闭包的并集） | {C}（B读1→C） | 否 |
| {A,B,D,F} | {A,B,D,F}（A读0→A，B读0→B，D读0→F，F读0无转移） | {C}（B读1→C） | 是（包含F） |
| {C} | {C}（C读0→C） | {B,D}（C读1→B，取B的ε-闭包） | 否 |
| {B,D} | {B,D,F}（B读0→B，D读0→F，取二者ε-闭包的并集） | {C}（B读1→C） | 否 |
| {B,D,F} | {B,D,F}（B读0→B，D读0→F，F读0无转移） | {C}（B读1→C） | 是（包含F） |
| ∅ | ∅ | ∅ | 否 |
步骤4：简化DFA（可选）
观察转移关系，{A,B,D,F}和{B,D,F}的转移行为一致，但初始到达路径不同，无法合并；其他状态也无重复行为，最终DFA即为上述表格所示。
内容的提问来源于stack exchange，提问作者coder2410
相关产品推荐
相关产品推荐
