3

什么是通过语言 {0,1} 接受所有内容但没有子字符串 110 或 101 的正则表达式？

接受：

  • 111111
  • 000011111
  • 100001000001001
  • 010
  • 1

拒绝：

  • 100110
  • 010100
  • 123

编辑：根据下面对答案的评论，这个问题要求一个正式的正则表达式。

4

6 回答 6

11

这是解决方案（即使没有前瞻）：

/^0*(11*$|10$|100+)*$/
  • 从任意数量的零开始。
  • 循环（知道：到目前为止解析的字符串不以“1”或“10”结尾）
    • "1$" 没问题 (&stop)
    • 如果你找到“11”，那么在你读完之前你不能读任何东西
    • “10 美元”没问题。
    • 如果您阅读“10”并想继续阅读，请阅读一个或多个零。然后回到循环。
于 2009-11-08T15:08:55.870 回答
6

你最好检查它是否不匹配/101|110/

于 2009-11-08T14:45:19.957 回答
4

假设您的正则表达式引擎支持前瞻，这似乎可行。

/^(1(?!01|10)|0)*$/
于 2009-11-08T15:01:24.403 回答
3

仅限于正式的正则表达式表示法：

((1|0*|0*1)(000*))*0*(10*|1*)
于 2009-11-09T16:33:28.213 回答
-1

这应该有效：

/^([01])\1*$/
于 2009-11-08T14:46:24.713 回答
-1

对应的 DFA 很容易绘制。

当受到公认的“正式”正则表达式语法的限制时，没有相应的有限大小的正则表达式（缺少完整代数中必需的“and”、“xor”、“not”等琐碎的运算符）

但是有很多解决方案，比如这个

(0|100|(1|10|11*)$)*

它也可以通过所有格匹配来解决。(111+$) 是 111++

于 2010-12-30T21:54:12.993 回答