正则表达式排除 101 和 110
接受语言 {0,1} 上的所有内容但不包含子字符串 110 或 101 的正则表达式是什么?
接受:
- 111111
- 000011111
- 100001000001001
- 010
- 1
拒绝:
- 100110
- 010100
- 123
编辑:根据下面答案的评论,这个问题要求一个正式的正则表达式。
What is a regexp that accepts everything over the language {0,1} but has no substring 110 or 101?
Accept:
- 111111
- 000011111
- 100001000001001
- 010
- 1
Reject:
- 100110
- 010100
- 123
Edit: Per comments on answers below, this question is asking for a formal regular expression.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(6)
这就是解决方案(即使没有前瞻):
This is the solution (even without lookahead):
您最好检查它是否不匹配
/101|110/
You'd be best off checking if it doesn't match
/101|110/
假设您的正则表达式引擎支持前瞻,这似乎可行。
This seems to work, assuming that your regex engine supports lookahead.
仅限于正式的正则表达式表示法:
Limited to formal regular expression notation:
这应该有效:
This should work:
相应的DFA很容易画出来。
当受到公认的“正式”正则表达式语法的限制时,没有相应的有限大小的正则表达式(缺乏完整代数中必需的“and”、“xor”、“not”等琐碎运算符)
但是有很多解决方案,像这样的
(0|100|(1|10|11*)$)*
也可以通过所有格匹配来解决。 (111+$) 是 111++
The corresponding DFA is easy to draw.
There is no corresponding regex of finite size when being limited by the accepted "formal" regex syntax (lack of trivial operators like "and", "xor", "not" which are necessary in a complete algebra)
But there are many solutions , like this one
(0|100|(1|10|11*)$)*
It can be solved with possessive matching too. (111+$) is 111++