大门| 2007大门|问题71

考虑正则表达式r=（a+b）*（AA+BB）（A+B）*BR>

下面给出的哪个正则表达式定义的语言与正则表达式R定义的语言相同？ （A） （a（ba）*+b（ab）*）（a+b） ⁺ （B） （a（ba）*+b（ab）*）*（a+b）* （C） （a（ba）*（a+bb）+b（ab）*（b+aa））（a+b）* （D） （a（ba）*（a+bb）+b（ab）*（b+aa））（a+b） ⁺ 答复: （C） 说明： B空的可以接受，而不是给定的–>

上述DFA可以通过在状态B和C处解析循环，并在最终状态处移除额外的转换来简化，如下所示：

为了从B到达最终状态，我们可以让字母“a”移动到状态D，或者让字母“bb”移动到状态E。 类似地，为了从C到达最终状态，我们可以让字母“b”移动到状态E，或者让字母“aa”移动到状态D。

因此，正则表达式是： （a（ba）*（a+bb）+b（ab）*（b+aa））（a+b）*

a（ba）*（a+bb）：从a移动到B，并移动到任意一个最终状态 b（ab）*（b+aa）：从A移到C，C移到任意一个最终状态 注：对于此类问题，我们也可以使用选项消除法，即如果我们

至少找到这样一个字符串，它不会验证正则表达式。 选项（A）接受ab，但给定的正则表达式不接受ab。 选项（B）接受空字符串，但给定的正则表达式不接受。 选项（D）不接受aa，但给定的正则表达式接受aa。

这个解决方案是由 安田荣彦 这个问题的小测验