查找其他描述的语言的正则表达式
设{ab}为字母集，写出正则表达式：
1) 所有a和b的个数均为奇数的单词的语言；
2) 所有长度为奇数并且包含子串ab 的单词的语言。
另外，如果可能的话，请帮我找到两种不同的表达方式，以帮助加强我对如何解决此类问题的理解。
Letting {a b} be the alphabet set, write a regular expression for:
1) The language of all those words in which the number of a's and the number of b's are both odd;
2) The language of all those words whose length is odd and which contain the substring ab.
Also, if possible, please help me find two different expressions for each so as to help strengthen my understanding of how to go about solving such problems.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
对于第一个，您可以构建一个简单的 4 状态 DFA 来识别该语言。然后，您可以使用可从 Kleene 定理（他说 FA 识别的所有语言都是由 RE 生成的部分）中恢复的算法来获得有效的 RE……或者只是从图表中推理出来。
对于第二个，你知道 (ab) 是 RE 的一部分；现在，您需要考虑所有可以向其添加奇数个字符（正面或背面）的独特方法，并用 + 连接所有这些可能性，以获得简单、正确的 RE。
我认为没有人特别喜欢只给你答案的想法。
编辑：
现在已经过去了一段时间，我将完成第一个问题的答案，向感兴趣的读者展示如何做到这一点。
我们的第一个 FA 是这样的：
我们将从中删除状态并用正则表达式替换 s 以覆盖该状态。我们从一个简单的开始......让我们摆脱 OE。这是表格...
在继续之前先说服自己这是正确的。接下来，我们去掉EO：
为了让下一步更简单，我们引入一个新的起始集X和一个新的接受状态Y； OO不再接受。我们消除了对 OO 的需要：
因此，最终的正则表达式是
我们可以开始尝试列出生成的最小字符串，就像基本的健全性检查一样： {ab, ba, aaab, aaba, bbab, bbba, abaa, abbb, baaa , babb, ...} 我觉得不错！
每个步骤的减少规则可以形式化，或者您可以应用仔细的推理来确保您得到正确的结果。检查克莱恩定理的证明以进行仔细分析。另外，马丁的形式语言简介或其他东西有使用此算法的很好的例子。
For the first one, there's an easy 4-state DFA you can construct to recognize the language. Then, you can use the algorithm recoverable from Kleene's theorem (the part where he says all languages recognized by a FA are generated by a RE) to get an RE that works... or just reason it out from the diagram.
For the second one, you know that (ab) is part of the RE; now, you need to think of all the unique ways you could add an odd number of characters to this (front or back), and connect all those possibilities with + for an easy, correct RE.
I don't think anybody particularly likes the idea of just giving you the answer.
EDIT:
So now that some time has passed, I'll work through the answer to the first one to show interested readers how it can be done.
Our first FA is this:
We will remove states from this and replace s with a regular expression to cover that state. We start with an easy one... let's get rid of OE. Here's the table for that...
Convince yourself this is correct before continuing. Next, we get rid of EO:
To make the next step simpler, we introduce a new start set X and a new accepting state Y; OO is no longer accepting. We eliminate the need for OO:
Therefore, the final regex is
We can begin trying to list the smallest strings this generates, just as a basic sanity check: {ab, ba, aaab, aaba, bbab, bbba, abaa, abbb, baaa, babb, ...} Looks good to me!
The rules for reducing at each step can be formalized, or you can just apply careful reasoning to ensure that you're getting the right thing. Check a proof of Kleene's theorem for a careful analysis. Also, Martin's Introduction to Formal Languages or something has good examples of using this algorithm.