我被这个练习问题难住了（不是为了分数）：
{w 是 {a,b}* 的一个元素：a 的个数是偶数，b 的个数是偶数 }
我似乎无法弄清楚这一点。在这种情况下，0 被认为是偶数。一些可接受的字符串：{}、{aa}、{bb}、{aabb}、{abab}、{bbaa}、{babaabba} 等
我做过类似的例子，其中 a 必须是前缀，答案是：(aa) (bb) 但在这种情况下，它们可以按任何顺序排列。
可以使用 Kleene 星 (*)、并集 (U)、相交 (&) 和串联。
编辑：这个也有问题
{w 是 {0,1}* 的一个元素：w = 1^r 0 1^s 0 对于某些 r,s >= 1}
这有点难看，但它应该可以工作：
ε U ( (aa) U (bb) U ((ab) U (ba) (ab) U (ba)) )*
对于第二个：
11*011*0
通常我会使用a+而不是在aa*这里。
编辑：未删除的回复：NullUserException 答案中的评论。
1）我个人认为如果您首先构建一个可以接受字符串的DFA，这个更容易概念化。我还没有把它写下来，但在我脑海中，我认为你可以用 4 个状态和一个接受状态来做到这一点。从那里您可以通过使用诸如this one的算法一次删除一个状态来创建等效的正则表达式。这是可能的，因为 DFA 和正则表达式可证明是等价的。
2) 考虑 Kleene 星仅适用于最近的正则表达式这一事实。因此，如果您有两个单独的未分组原子（一个原子本身就是一个正则表达式！），它只适用于第二个（如，ab*将匹配单个 a，然后匹配任何数字 - 包括 0 - b）。在您希望某些东西存在但不确定有多少的情况下，您可以利用它来发挥自己的优势。