没有重复数字的数字字符串的正则表达式？
我正在通读dragon book并尝试解决如下所述的练习
为以下语言编写常规定义：
- 所有没有重复数字的数字字符串。提示:请先用几个数字尝试解决此问题，例如{ 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 | ...因此，必须用d10编写10!替代方案。既然我们要写这个常规的定义，我怀疑这是一个合适的解决方案。你能帮帮我吗？
回答 7
Stack Overflow用户
发布于 2011-09-26 04:14:47
所以问题并不一定要求你写一个正则表达式，它要求你提供一个正则定义，我将其解释为包括NFA的定义。事实证明，你使用哪一个并不重要，因为所有的NFA都可以在数学上等同于正则表达式。
使用数字0、1和2，有效的NFA将如下所示(对于简陋的图表，很抱歉)：
每个状态代表输入中扫描的最后一个数字，并且在任何节点上都没有循环，因此这是集合{0,1,2}中没有重复数字的字符串的准确表示。扩展它是微不足道的(尽管它需要一个大的白板:)。
注意:我假设字符串"0102“是有效的，但字符串"0012”不是。
通过使用here描述的算法，可以将其转换为正则表达式(尽管这将是痛苦的)。
Stack Overflow用户
发布于 2011-09-26 01:19:00
以下是一种可能的构造：
- 最多包含一个'0‘数字的字符串的正则表达式看起来像( 1-9 )* (0| epsilon ) ( 1-9 )* -所以任何数量的1-9数字，后面跟着0或1 '0’，后面跟着任何数量的1-9数字。
- 我们现在可以注意到，如果只有一个'1‘数字，它将在’0‘数字(或代表缺少的零数字的epsilon)的左边或右边。所以我们可以构造一个将这两个大小写或(|)放在一起的正则表达式，我们现在可以进一步向下钻取，如果只有一个'2‘数字，它可以在1数字的右边或左边，它是相对于'0’数字的两个可能的位置，所以我们正在构建一个二叉树，ORed正则表达式的数量大约是2^10的数量级，这与接受这种语言的有限状态机的数量是一样的。一个接受语言的有限状态机应该有(2^10 + 1)个状态，每个状态n都可以看作它的二进制表示n0n1n2n3n4n5n6n7n8n9，意思是n0 =可见数字'0'，n1 =可见数字'1‘。以及转换到单个非接受状态的重复数位。初始状态为零。
如果允许补码，则包含多个'0‘数字的正则表达式将为(0-9)* 0 (0-9)* 0(0-9)*0 (0-9)*，对所有数字重复此操作，补码。
对于彼得·泰勒来说，你绝对可以更简洁地解释，没有两个连续的数字是相同的。显然，这个问题的状态要小得多。
SUCCINCTNESS OF THE COMPLEMENT AND INTERSECTION OF REGULAR EXPRESSIONS
“2中的一项研究表明，在实践中使用的大多数一次明确的正则表达式都具有非常简单的形式:每个字母符号最多出现一次。我们将这些符号称为单次出现的正则表达式(SORE)，并显示出交集的严格指数下界。”
..。
在本节中，我们展示了在定义单个正则表达式的补码时，通常无法避免双指数大小的增加。相反，当表达式是一种明确的补码时，可以在多项式时间内计算其补码。
Stack Overflow用户
发布于 2011-09-25 11:04:22
与其试图写一个只定义你想要的东西的定义，不如你告诉它生成一个长达10位的所有字符串的列表，包括重复的数字，然后减去包含两个0，两个1的字符串……等等？这样行得通吗？
https://stackoverflow.com/questions/7547583
复制相似问题