这是一个家庭作业问题：
Is L_4 Regular?
Let L_4 = L*, where L={0^i1^i | i>=1}.
我知道 L 是非常规的，并且我知道 Kleene Star 是一个封闭的操作，所以我的假设是 L_4 是非常规的。
然而，我的教授提供了一个上面的例子L = {0^p | p is prime}，他说这是规则的，通过证明这L*等于L(000* + e)说每个都是彼此的子集（在这种情况下，e 表示空词）。
所以他的方法涉及形成一个正则表达式0^p，但是当我基本上已经有了一个正则表达式时，我该怎么做呢？
常规语言在 Kleene 星下关闭。也就是说，如果语言 R 是正则的，那么 R* 也是正则的。
但是这个推理在另一个方向上不起作用：有一些非常规语言 P，其中 P* 实际上是正则的。
您在问题中提到了一个这样的 P：字符串 0^p 的集合，其中 p 是素数。
很容易将泵引理用于常规语言和上下文无关语言，以表明 P 至少是上下文敏感的。但是，P* 等价于语言 0^q，其中 q 是零个或多个素数之和。但是对于 q=0（空字符串）和任何 q>=2 都是如此，因此 P* 可以用三态 DFA 来识别，即使 P 本身不是正则的。
因此，L 与上下文无关与您的 L_4 = L* 是否是常规的无关。如果您可以构造一个识别 L_4 的 DFA，就像我在上面对 P* 所做的那样，那么显然它是常规的。在尝试找到有效的 DFA 的过程中，您可能会看到一些模式出现，可以用作抽水论证的基础。Myhill-Nerode 定理是证明语言非常规的另一种方法，如果该语言适合分析前缀和区分扩展名，则该定理很有用。如果该语言可以在某种关系下分解为一组有限的等价类，那么它就可以用包含那么多状态的 DFA 来识别。
Edit: For anyone wondering whether OP's example L_4 is regular or not...it's not, which can be proved using the pumping lemma for regular languages.
Assume L_4 is regular, with "pumping length" P. Consider the string w=0P1P, which is an element of L_4. We need to decompose it into the form w=xyz, with |y| >= 1 and |xy| <= P. Any choice of xy fulfilling these conditions will consist of all zeroes. But then any string w' = xynz with n != 1 will have mismatched counts of 0s and 1s, and therefore cannot be an element of L_4. So the pumping lemma does not hold, and L_4 cannot be regular.