GATE | GATE-CS-2006 |问题34

考虑正则语言L＝（111＋11111）*。任何DFA中接受这种语言的州的最小数量为： （A） 3. （B） 5. （C） 8. （D） 9 答复: （D） 说明： 有限状态自动机是：

说明：

给出了语言L=（111+11111）* 属于该语言的字符串是 L={null，111，11111，111111，11111111111，111111111111，1111111111111，…..形成字符串长度8，（1的数量），现在我们可以从长度3和5生成任意长度的字符串（即长度8，长度9，长度10，长度11，…） L={null，111111111111111111111111111111111*} 字符串的长度，属于该语言 L={0,3,5,6,8,9,10,11，…} 所以，有5个状态是终态，4个状态是非终态 因此，州总数为9个州。 因此，选项D是正确的。 这一解释由纳米塔·辛格提供。 这个问题的小测验