正则表达式的最小长度
在做课堂作业时，我想到了这个问题：
对于以下每个正则表达式，给出最小长度的字符串 不是表达式定义的语言。
(bb)*(aa)*b*a*(bab)*∪b∪ab
我要去尝试仅在第一个问题上获得帮助，看看我是否能找出第二个问题。我所知道的如下：Kleene * 表示 0 个或多个可能的元素。集合的并集是包含集合a和集合b的所有元素且没有重复元素的集合。通过插入 lambda 开始解决第一个问题，我得到：
第一次运行： bbaab
第二：bbbbaabaabbaabbbbaab
第三： bbbbbbaabaabbaabbbbaabaabbbbaabaabbaabbbbaabbbbbbaabaabbaabbbbaab
如果我做得正确，那么长度为 0 到 5 的字符串不在该语言中。我这样做正确吗？
Working on my homework for a class and I came to this question:
For each of the following regular expressions, give minimal length strings that are
not in the language defined by the expression.
(bb)*(aa)*b*a*(bab)*∪b∪ab
I'm going to try to only get help on the first one and see if i can figure out the second. Heres what I Know: Kleene * indicates 0 or more possible elements. and union of a set is the set containing all elements of set a and set b without repeating an element. Working through the first problem starting by inserting lambda, i get:
1st run: bbaab
2nd: bbbbaabaabbaabbbbaab
3rd: bbbbbbaabaabbaabbbbaabaabbbbaabaabbaabbbbaabbbbbbaabaabbaabbbbaab
If I'm doing that correctly than strings of length 0 to 5 are not in the language. Am i doing this correctly?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
第一个正则表达式匹配以偶数个“b”（包括零）开头、后跟偶数个“a”（零也可以）、然后再跟一些“b”的任何单词。
这意味着空字符串以及字符串“b”都在该语言中。
然而，字符串“a”不在该语言中。
因此，所有不在该语言中的最小长度字符串都是“a”。
第二个正则表达式匹配“”、“a”和“aa”（通过 a*(bab)*）以及“b”和“ab”。
但是它与“ba”和“bb”不匹配。
因此，最小字符串的长度为 2：“bb”和“ba”。
The first regular expression is matching any word that starts with an even number of 'b's (zero included) followed by an even number of 'a's (zero is ok), then followed by some 'b's.
This means that the empty string is in the language, as well as the string "b".
However, the string "a" is not in the language.
Thus all the minimal length string that are not in the language is "a".
The second regex matches on "", "a" and "aa" (by a*(bab)*) and also on "b" and "ab".
However it doesn't match on "ba" and "bb".
Thus the minimal strings are of length 2: "bb" and "ba".