正则表达式 – 没有重复数字的数字字符串的正则表达式？

发布时间：2020-12-14 06:33:46 所属栏目：百科来源：网络整理

导读：我正在阅读 dragon book，并尝试解决如下的演习 Write regular definitions for the following languages: All strings of digits with no repeated digits. Hint: Try this problem first with a few digits,such as { 0,1,2 }. 尽管已经尝试解决了几个小时

我正在阅读 dragon book，并尝试解决如下的演习

Write regular definitions for the following languages:

All strings of digits with no repeated digits. Hint: Try this problem first with a few digits,such as { 0,1,2 }.

尽管已经尝试解决了几个小时，我无法想象一个解决方案，除了非常冗长的话

d0 -> 0?
d1 -> 1?
d2 -> 2?
d3 -> 3?
d4 -> 4?
d5 -> 5?
d6 -> 6?
d7 -> 7?
d8 -> 8?
d9 -> 9?
d10 -> d0d1d2d3d4d5d6d7d8d9 | d0d1d2d3d4d5d6d7d9d8 | ...

因此不得不写10！ d10中的替代品由于我们写这个常规定义，我怀疑这是一个正确的解决方案。你能帮我吗？

所以这个问题不一定要求你写一个正则表达式，它要求你提供一个定义，我将其解释为包括NFA的。事实证明，您使用的是无关紧要的，因为所有NFA都可以在数学上显示为正则表达式。

使用数字0，1和2，有效的NFA将是以下(对于令人难过的图表)：

每个状态表示在输入中扫描的最后一个数字，并且在任何节点上没有循环，因此这是一个字符串的精确表示，没有来自集合{0,2}的重复数字。扩展这是微不足道(虽然它需要一个大的白板:))。

注意：我假设字符串“0102”有效，但字符串“0012”不是。

这可以通过使用所描述的算法here转换为正则表达式(虽然会很痛苦)。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!