如何为自定义规则的实数正则表达式构造确定有限自动机（DFA）

嘿，我来帮你一步步搞定这个实数对应的DFA构造～先从修正你的正则表达式开始吧——你写的O应该是0，而且正则里的小数点需要转义成\.，修正后的正确正则是：/[+-]?(0|[1-9][0-9]*)\.[0-9]+/，完全匹配你描述的规则：可选正负号开头，接着是单个0或者非零开头的数字序列，然后是小数点，最后必须跟非空的数字串。

先把每个状态的含义明确下来，这样状态转移逻辑会非常清晰：

• S0（初始状态）：还未读取任何字符，等待输入正负号、数字0或非零数字
• S1（已读取正负号）：已经读到+或-，接下来只能读0或者非零数字
• S2（已读取整数部分的单个0）：已经读到独立的0（不管前面有没有正负号），接下来必须读小数点
• S3（已读取整数部分的非零开头数字）：已经读到1-9中的一个，后续可以继续读任意数字，或者切换到小数点
• S4（已读取小数点）：已经读到小数点，接下来必须读至少一个数字
• S5（已读取小数部分的至少一个数字）：已经读到小数点后的第一个数字，后续可以继续读任意数字，这是接受状态（只要输入结束时停在这里，字符串就是有效的）

下面是每个状态针对不同输入的转移目标（所有未列出的输入都会进入拒绝状态，也就是sink状态，一旦进入就无法再转移到其他状态）：

• 从S0出发：
  • 输入+或- → 转移到S1
  • 输入0 → 转移到S2
  • 输入1-9 → 转移到S3
• 从S1出发：
  • 输入0 → 转移到S2
  • 输入1-9 → 转移到S3
• 从S2出发：
  • 输入. → 转移到S4
• 从S3出发：
  • 输入0-9 → 留在S3（继续读取整数部分的后续数字）
  • 输入. → 转移到S4
• 从S4出发：
  • 输入0-9 → 转移到S5
• 从S5出发：
  • 输入0-9 → 留在S5（可以继续读取任意多个小数位）

我们用几个典型字符串验证一下这个DFA的逻辑：

• 有效串：+0.123 → S0→S1→S2→S4→S5（最终停在接受状态，有效）
• 有效串：123.45 → S0→S3→S3→S3→S4→S5→S5（最终停在接受状态，有效）
• 无效串：012.3 → S0→S2，接下来读1进入拒绝状态（整数部分不能是0开头的多位数，无效）
• 无效串：123. → S0→S3→S3→S3→S4，输入结束停在S4（小数点后没有数字，无效）
• 无效串：-.123 → S0→S1，接下来读.进入拒绝状态（缺失整数部分，无效）

如果需要简化，你可以把所有拒绝情况合并成一个通用的sink状态，这样整个DFA的状态总数就是7个（S0-S5 + 拒绝状态），逻辑上会更简洁。

内容的提问来源于stack exchange，提问作者Pik