regex - 0 和 1 相等的正则表达式

Question

如何找到具有相同数量的 1 和 0 的正则表达式。
我也对你如何看待这种解决方案感兴趣？

例子:
应该匹配: 1100, 00100111 , 01 。
不应该匹配: 110 , 0, 11001。

我需要正则表达式，它给出了所有这些字符串的集合。
如果集合中的字符串长度由 2n 中的正则表达式给出然后数量0s应该等于数字 1s = n .

Answer 1

无法为语言 L = (0,1)(1 和 0 的数量相同)生成正则表达式。这不是正则语言，因此不能用正则表达式来描述。它不规则，因为接受它的自动机将需要不同数量的内存，具体取决于输入的长度。常规语言是一种使用常量内存的语言，而不管输入的长度如何。您描述的语言可以由上下文无关文法生成，但不能由正则表达式生成。
下面的 CFG 生成字符串，其中 0 的数量和 1 的数量相等。如果 S 是语言中的任何单词:
S -> SS; S -> 0S1; S -> 1S0; S -> e 空词
对于这种语言，您需要一个堆栈，并且可以设计一个下推自动机来接受它，或者一个图灵机。