regex - 正则表达式的最小长度

Question

为一堂课做作业，我想到了这个问题：

对于以下每个正则表达式，请给出不在表达式定义的语言中的最小长度字符串。

1. (bb)*(aa)*b*
2. a*(bab)*∪b∪ab

我将尝试只在第一个上获得帮助，看看我是否能弄清楚第二个。这是我所知道的：Kleene * 表示 0 个或多个可能的元素。集合的并集是包含集合 a 和集合 b 的所有元素而不重复元素的集合。从插入 lambda 开始解决第一个问题，我得到：

第一次运行：bbaab
第二次：bbbbaabaabbaabbbbaab
第三次：bbbbbbaabaabbaabbbbaabaabbbbaabaabbaabbbbaabbbbbbaabaabbaabbbbaab

如果我做得正确，那么长度为 0 到 5 的字符串不在该语言中。我这样做正确吗？

Answer 1

第一个正则表达式匹配任何以偶数个 'b'（包括零）开头的单词，然后是偶数个 'a'（零是可以），然后是一些 'b'。

这意味着空字符串在语言中，以及字符串“b”。但是，字符串“a”不在该语言中。

因此，所有不在该语言中的最小长度字符串都是“a”。

---

第二个正则表达式匹配“”、“a”和“aa”（通过 a*(bab)*）以及“b”和“ab”。但是它与“ba”和“bb”不匹配。

因此，最小字符串的长度为 2：“bb”和“ba”。