大门|大门-CS-2005 |问题53

考虑机器M： M认可的语言是： （A） {w∈ {a，b}*/w中的每个a后面紧跟着两个b} （B） {w∈ {a，b}*w中的每个a后面至少有两个b’} （C） {w∈ {a，b}*w包含子字符串’abb’} （D） {w∈ {a，b}*w不包含’aa’作为子字符串} 答复: （B） 说明：

这里是w∈ {a，b}*意味着w可以是{a，b}*集合中的任何字符串，{a，b}*是由a和b（你能想到的a和b的任何字符串）组成的所有字符串的集合，比如null，a，b，aaa，abbaaa，bbbbb，AAAA，AAABBBBBBBBABABAB等。

这些类型的问题在GATE中经常被问到，在GATE中，它被要求在选项中选择最适合的语言。为了解决这样的问题，有一种更好的方法，我们尝试通过智能地选择测试字符串来消除错误的选项，直到剩下一个正确的选项。正如前面提到的，让我们试着消除选项（A），它承认 只有thos E 一串 （由a和b组成），其中w中的每个a后面紧跟着两个b，所以如果我们取字符串abbb（三个b），那么它被机器接受，所以这个选项是错误的。现在我们试图消除选项（C），它只识别w包含子字符串“abb”的那些字符串（由a和b组成），所以如果我们使用字符串abbaa（有子字符串abb），那么机器不接受它，所以这个选项也是错误的。现在我们试图消除选项（D），它只识别那些w不包含“aa”的字符串（由a和b组成）作为子字符串，所以如果我们将字符串abbaba（“aa”不作为子字符串），那么它不被机器接受，所以这个选项也是错误的。我们剩下的唯一选项是选项（b），其中w中的每个a后面至少有两个b’是正确的。所以答案是选项（B）。

这个解决方案是由 N 伊马尔·巴拉德瓦伊。

这个问题的小测验