相同发生的1和2，但长度< 1.000.000

Question

因此，我有以下任务，其中我必须解释是否可以在这些约束条件下构建正则表达式：

数字N< 1.000.000，它包含的数字1与数字2一样多

我的任务不是真正地编写正则表达式，而是对这个事实进行推理，如果可能的话。

我的结论是，这是完全可能的，但我必须在正则表达式中写下每一个可能的字符串，这将是非常长的。

到目前为止，我有以下正则表达式：

((3-9*1{n}3-9*2{n}3-9*){0,000})

其中n的最大长度为1.000.000。

我知道迭代器不是常规语言中的“东西”。但是，是否有一种更简单的方法来“迭代”n，而不是只需要手工编写它呢？

Answer 1

我的结论是，这是完全可能的，但我必须在正则表达式中写下每一个可能的字符串，这将是非常长的。

对于有关理论的问题，它将是非常长的事实是不相关的。你说得对。任何有限的语言都是规则的。

我知道迭代器不是常规语言中的“东西”。但是，是否有一种更简单的方法来“迭代”n，而不是只需要手工编写它呢？

不，没有。也许思考如何构造一个状态机是有帮助的。

一种状态，即初始状态，是这样一种状态:所见的1数与所见的2数相等。

第二种状态是一个比1多一个2的状态。

第三种状态是一个比2多一个1的状态。

第四种状态是一个比2多两个2的状态.

要使自己确信不能组合任何这些状态，应该是相当简单的，因为每个状态的有效剩余子字符串不存在重叠。因此，您需要>1000000个状态，并且由于正则表达式转换到状态机是相当直接的，正则表达式的复杂性不能低于状态机的复杂性。

当然，在编程时，您可以更有效地实现这一点。例如，您可以将1s和2s的计数存储在其他变量中。但是变量是一个功能状态机没有的。