这种语言是 REGULAR / CONTEXT FREE 但不是 REG / Nothing 吗？

Question

(1) {((a^2)(b^4)ab)^(3k) : k>=0}

(2) {a^(2n)b^(3n) : n >= 7}

(3) {a^(2n)b^(3n) : n <= 7}

1) 没有这方面的线索。

2) 我认为它是 contextFree 因为对 n 没有限制，不像 3) 我们不能构建 finit 自动化但我们可以构建语法 :

S ---> (a^14)X(b^21)

X ---> aabbb | aaXbbb

3) 对我来说，它是一种常规语言，因为 n 值的限制允许我们用自动化来表示它。

Answer 1

(1) 是正规的。一个正则表达式是：

(aabbbbabaabbbbabaabbbbab)*

(2) 是上下文无关的，但不是常规的。要查看它是否不规则，请在字符串上使用泵送引理：

a^(14p) b^(21p)

争辩说抽水只改变了 a 的数量。要查看它是上下文无关的，这是一个 CFG：

S := a^14 b^21 | aaSbbb

(3) 这是正则的，因为它是由以下八个词组成的有限语言：

e
a^2 b^3
a^4 b^6
a^6 b^9
a^8 b^12
a^10 b^15
a^12 b^18
a^14 b^21

Is this languages REGULAR / CONTEXT FREE but not REG / Nothing?