regex - 具有给定长度和确切字符数的正则表达式

Question

我正在寻找 $w\in {a,b}^n$ 具有确切数量ka的语言的正则表达式。

我几乎被困在这一点上。对于各种长度，使用 ${{b}^*a{b}^*}^k$ .

有人对我如何实现这样的正则表达式有任何建议吗？

score 2 · Accepted Answer

我会用这个：

(b*ab*){k}

它只是使 k 块恰好包含一个 a。因此单词有 k a。b* 之一可以在左侧或右侧被分解。

score 1 · Accepted Answer

对此没有简单的解决方案。

虽然这种语言是常规的，但很难描述。您可以通过将两种语言 ((a|b)^n和b*(ab*)^k) 的（平凡的）DFA 相互交叉来获得它，但是您将获得带有(n-k)*k状态的 DFA。并将其转换为正则表达式不会使其变得更好。

但是，如果您正在寻找一个实际的实现，它会变得容易得多。您可以简单地针对两个正则表达式测试输入，或者您可以使用前瞻将它们组合成一个正则表达式：

/^(?=[ab]{n}$)b*(ab*){k}$/

score 0 · Accepted Answer

您可以使用前瞻来强制执行总长度：

^(?=.{5}$)([^a]*a){2}[^a]*$

3 回答 3