如何找到数量相等的 1 和 0 的正则表达式。我也对您如何看待这种解决方案感兴趣？
例如：应该匹配：1100、00100111、01。不应该匹配：110、0、11001。
我需要正则表达式，它给出了所有这些字符串的集合。如果集合中的字符串长度由正则表达式给出，2n则 number of0s应等于 number 1s = n。
user801154
问问题
14549 次
4 回答
11
无法为语言 L = (0,1)（相同数量的 1 和 0）生成正则表达式。这不是正则语言，所以不能用正则表达式来描述。这不是常规的，因为接受它的自动机将需要不同数量的内存，具体取决于输入的长度。常规语言是一种使用恒定内存的语言，无论输入的长度如何。您描述的语言可以由上下文无关语法生成，但不能由正则表达式生成。以下 CFG 生成字符串，其中 0 的数量和 1 的数量相等。如果 S 是语言中的任何单词：S -> SS；S -> 0S1；S -> 1S0; S -> e 空词 对于这种语言，您需要一个堆栈，并且可以设计一个下推自动机来接受它，或者一个图灵机。
于 2016-05-18T10:59:27.140 回答
3
常规语法（有限状态自动机）不可能：http ://en.wikipedia.org/wiki/Regular_language
于 2012-09-19T15:24:16.583 回答
3
这是满足您需求的 .NET 引擎的正则表达式模式。在ideone.com上查看它的实际应用。
^((?(D)(?!))(?<C>1)|(?(D)(?!))(?<-C>0)|(?(C)(?!))(?<D>0)|(?(C)(?!))(?<-D>1))*(?(C)(?!))(?(D)(?!))$
它通过使用两个堆栈来工作，如果当前的 1 多于 0，则使用一个 (C)，如果零多于一，则使用另一个 (D)。
不漂亮，绝对不可用，但它有效。（哈！）
于 2013-02-12T15:36:22.900 回答
1
虽然这对于另一个答案中所述的常规语法是不可能的，但扫描字符串应该相对容易，为 each 递增一个计数器1并为 each 递减它0。如果最终计数为 0，则0s 和1s 的数量相等（模 2^wordsize - 注意溢出会使它有点棘手，但取决于是否可以对输入做出其他假设，即可能没有必要）。
于 2012-09-19T15:41:45.153 回答