regex - 如何使用语法或正则表达式识别以下字符串组？

Question

我唯一注意到的是每个 n 的元素数是Catalan Number。

我们只有偶数。这个列表无限地继续下去。

n=2
ab

n=4
aabb
abab

n=6
aaabbb
aababb
aabbab
abaabb
ababab

n=8
aaaabbbb
aaababbb
aaabbabb
aaabbbab
aabaabbb
aabababb
aababbab
aabbaabb
aabbabab
abaaabbb
abaababb
abaabbab
ababaabb
abababab

该列表可以通过以下 python 代码生成：http: //pastebin.com/hynjWTrp

Answer 1

没有正则表达式，因为我们的语言不是正则的。

匹配 a 和 b 的通用形式与匹配括号相同，它是无上下文语法：

S -> e | AS
A -> e | aAb

e空字符串在哪里。