使用闭包性质证明正则性
这是一个家庭作业问题：
Is L_4 Regular?
Let L_4 = L*, where L={0^i1^i | i>=1}.
我知道 L 是非常规的，并且我知道 Kleene Star 是闭运算，所以我的假设是 L_4 是非常规的。
然而，我的教授提供了一个上述示例，其中 L = {0^p | p 是素数}，他通过证明 L* 等于 L(000* + e) 来证明这是正则，因为每个都是彼此（e 在这种情况下意味着空词）。
所以他的方法涉及形成 0^p 的正则表达式，但是当我基本上已经有了一个正则表达式时，我该如何做到这一点呢？
Here's a homework problem:
Is L_4 Regular?
Let L_4 = L*, where L={0^i1^i | i>=1}.
I know L is non-regular and I know that Kleene Star is a closed operation, so my assumption is that L_4 is non-regular.
However my professor provided an example of the above in which L = {0^p | p is prime}, which he said was regular by proving that L* was equal to L(000* + e) by saying each was a subset of one another (e in this case means the empty word).
So his method involved forming a regex of 0^p, but how I can do that when I essentially have one already?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
常规语言在 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来识别。
编辑：对于任何想知道 OP 的示例 L_4 是否是正则的人......它不是，这可以使用正则语言的泵引理来证明。
假设 L_4 是规则的，具有“泵送长度”P。考虑字符串 w=0P1P，它是 L_4 的一个元素。我们需要将其分解为 w=xyz 的形式，
与 |y| >= 1 且 |xy| <= P。满足这些条件的 xy 的任何选择都将由全零组成。但是，任何 n != 1 的字符串 w' = xynz 将具有不匹配的 0 和 1 计数，因此不能是 L_4 的元素。因此泵送引理不成立，并且 L_4 不能是正则的。
Regular languages are closed under Kleene star. That is, if language R is regular, so is R*.
But the reasoning doesn't work in the other direction: there are nonregular languages P for which P* is actually regular.
You mentioned one such P in your question: the set of strings 0^p where p is prime.
It is easy to use the pumping lemmas for regular and context-free languages to show that P is at least context-sensitive.
However, P* is equivalent to the language 0^q, where q is the sum of zero or more primes.
But this is true for q=0 (the empty string) and any q>=2, so P* can be recognized with a 3-state DFA, even though P itself is not regular.
So L being context-free has no bearing on whether your L_4 = L* is regular or not. If you can construct a DFA that recognizes L_4, as I did for P* above, then clearly it's regular.
In the process of trying to find a DFA that works, you'll probably see some pattern
emerge that can be used as the basis for a pumping argument. The Myhill-Nerode theorem is another approach to proving a language non-regular, and is useful if the language lends itself to analysis of prefixes and distinguishing extensions. If the language can be decomposed into a finite set of equivalence classes under a certain relation, then it can be recognized with a DFA containing that many states.
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.