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

Question

我正在阅读龙书,试图解决一个如下所述的练习

编写以下语言的常规定义:

所有数字串都没有重复的数字.提示:首先使用几位数来尝试此问题,例如{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.既然我们将编写这个常规定义,我怀疑这是一个正确的解决方案.你能帮我吗？

Answer 1

所以问题并不一定要求你写一个正则表达式,它要求你提供一个常规定义,我将其解释为包括NFA.事实证明,使用哪个并不重要,因为所有NFA都可以在数学上与正则表达式相同.

使用数字0,1和2,有效的NFA将是以下(对于crummy图表抱歉):

在此输入图像描述

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

注意:我假设字符串"0102"有效,但字符串"0012"不是.

通过使用此处描述的算法,可以将其转换为正则表达式(尽管会很痛苦).

转换为现代正则表达式并不难,特别是如果您的目标是支持负前瞻断言中的反向引用的引擎(即递归引擎,例如PCRE).一个像`^(？:(？!([0-2])\ 1).)*$`的RE似乎是合适的(或者没有那样,扩大了负前瞻模式的可能性).如果没有负面的前瞻,regexp会非常痛苦,特别是对于更大的字母表... (2认同)