正则表达式匹配一个数字后跟一个重复多次的符号？

Question

如何创建可以匹配以下内容的正则表达式：

a3bbb
aaaa3bbb
a4bbbb
aaa5bbbbb

即a（一次或多次），然后是一个非负数，然后b重复'that many times'（与a之间的数字一样多和 b).

这种语言是正规的吗？如果没有，我们可以为此构建一个CFG吗？

编辑：至于是不是个位数，我说不是。（也正如Daniel Centore和rici所指出的，语言连CF都算不上。那么很自然的问题是，是context-sensitive还是unrestricted？）

Answer 1

如果数字是单个数字，则语言是规则的（因为您可以只列出九个可能的后缀）。但若数无界，则语不正。它甚至不是上下文无关的。所以正则表达式和CFG都不可用。

Answer 2

这种语言不规则（因此不能表示为 RegEx）。语言规律性的一项测试是检查它是否可以用有限自动机表示。可以证明，这种语言不能表示为 FA，因为 FA 至少需要与 a 和 b 之间的数量一样多的状态，但该数量不受限制。但是，如果它是有界的（ex 数字只能是 1-10）那么它将是 Regular。

该语言也不能表示为 CFG，这可能可以使用泵引理来表示。

Answer 3

就像其他答案所说的那样，如果数字是无限的，则语言既不是规则的（如果它是规则的，抽取引理表示对于足够长的字符串，b 可以独立于数字）也不是上下文无关的（如果它是上下文无关的，抽取引理表示对于足够长的数字，数字和 b 可以重复，但不正确）。

但是该语言是上下文相关的，因为它可以使用以下语法生成（为简单起见，我为 base-3 数字这样做，您可以扩展到 base 10）：

(1) S -> aS | aB
(2) B -> BN | N
(3) aN -> a0 | a1b | a2bb
(4) 0N -> 00 | 01b | 02bb
(5) 1N -> 10 | 11b | 12bb
(6) 2N -> 20 | 21b | 22bb
(7) bN -> WN
(8) WN -> WX
(9) WX -> NX
(10)NX -> Nbbb

规则 (1) 是生成 a 的

规则(2)是生成数字中的每个数字

规则(3)-(6)是将最左边的N替换为一个数字和相应的b个数。

规则 (7)-(10) 是让 N "consume" 的 b 在它的左边，并产生 3 b ( 10 b 以 10 为基数）。技术上 (7)-(10) 只是 bN -> Nbbb.

示例：

To generate: a102bbbbbbbbbbb (102 in base-3 = 11 in base-10)
S
aB (1b)
aBN (2a)
aBNN (2a)
aNNN (2b)
a1bNN (3b)
a1NbbbN (7)-(10)
a1NbbNbbb (7)-(10)
a1NbNbbbbbb (7)-(10)
a1NNbbbbbbbbb (7)-(10)
a10Nbbbbbbbbb (5a)
a102bbbbbbbbbbb (4c)

正则表达式匹配一个数字后跟一个重复多次的符号？

Regular expression to match a number followed by a symbol repeated that many times?

regex

grammar