regular-language - 当且仅当它是有限的 100 => n <= 0 时，语言 a^nb^2n 怎么可能是正则的？

Question

当且仅当它是有限的 100 => n <= 0 时，语言 a^nb^2n 怎么可能是规则的？

我知道当 n=>0 时（ a^nb^n ）这种形式的语言是不规则的，因为我们需要一个临时内存来跟踪 a 和 b 的数量，而且我知道每一种有限语言都是常规的，但我不明白是什么使类似形式的有限语言成为常规的？我们如何证明呢？我需要一些线索，除了能够获得其等效的正则表达式之外，我还需要一些更详细的解释..

谢谢

Answer 1

一个想法是考虑为该语言构建一个正则表达式：

ε ∪ abb ∪ aabbbb ∪ aaabbbbbb ∪ ... ∪ a ¹⁰⁰ b ²⁰⁰。

没错，所有有限语言都是正则的，而且由于这种特定的语言是有限的，所以它是正则的。

请注意，当且仅当您将 n 限制为 0 ≤ n ≤ 100 时，该语言不是规则的。相反，通过添加 0 ≤ n ≤ 100 的限制形成的语言是规则的。您还可以采取其他措施来限制语言以使其成为常规语言 - 例如，您可以使用 1,000 或 100,000 的上限。