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

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (21)

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,1,2}中没有重复的数字。扩展这一点很简单(尽管它需要一个大的白板:)。

注意:我假设字符串“0102”是有效的,但是字符串“0012”不是。

通过使用所描述的算法,可以将其转换为正则表达式。

用户回答回答于

这里有一个可能的结构:

  • 一个字符串的正则表达式,它最多包含一个“0”数字,看起来类似于(1-9)。*(0 Epsilon)(1-9)*-因此,任何数目的1-9位数,后面是零或1‘0位数,后面是任何数目的1-9位数。
  • 现在,我们可以通过注意到,如果只有一个“1”位数,它将要么位于“0”位的左边,要么位于“0”位的右边(或者表示缺失的零位数的epsilon)。因此,我们可以构造一个正则表达式,将这两种情况或‘ed()结合在一起。
  • 我们现在可以进一步钻研,如果只有一个“2”位数,它可以在1位数字的右边或左边,这是两个可能相对于“0”位的位置。
  • 因此,我们正在构建一个二叉树,所述正则表达式的数量为2^10,这与接受这种语言的FSM的顺序相同。接受该语言的FSM应该具有(2^10+1)状态,每个状态n都可以看作是它的二进制表示形式n0n1n2n3n4n5n6n7n8n9,意思是n0=看见数字‘0’,n1=看见数字‘1’,以及重复数字转换到单个不接受状态。初始状态为零。

如果允许补充,那么一个有超过一个‘0’位数的正则表达式将是(0-9)。*0(0-9)*0(0-9)*对所有数字重复,补语。

你绝对可以更加紧凑地解释没有两个连续的数字是相同的。显然,这个问题的政府规模要小得多。

扫码关注云+社区