我遇到了这个练习，我想了几个小时，但一无所获。
我们的字母表是{1...n}，我们的语言 Ln 包含下面的所有单词，Σ*因此语言中的每个单词都不包含字母表中的至少一个字母。
- 例如：如果 n=5，则该词
w={111223432}在该语言中，因为'5'该词中缺少该词。这个词w={1352224}不在语言中，因为所有的字母1...n都在这个词中。
我需要为这种有n+1状态的语言设计一个 NFA。
再一次，我尝试了一些事情，但并不是一个好主意。
问问题
141 次
1 回答
0
为简单起见，让我们对字母 {a, b, c} 执行此操作。想象一下，您的语言中有一个字符串。这意味着它缺少a，或者缺少b，或者缺少c（包括或）。如果我们知道丢失了哪个字符，那么使用单状态 NFA 来检查字符串是否从未包含该字符的副本将非常容易，该 NFA 由一个接受状态组成，该状态在除该字符之外的所有内容上都转换回自身。
由于字母表中只有有限多个字符，我们可以构建三个单态 NFA，每个 NFA 都旨在检查字符串是否缺少特定字符。
为了构建整个机器，让 NFA 的起始状态不确定地猜测缺少哪个字符，方法是将起始状态的 ε 转换添加到我们之前构建的每个单独的单态 NFA。您现在拥有该语言的四态 NFA。（您可以在这里看到它的图片。）希望不难看出如何将其推广到更大的字母大小！
于 2016-08-30T01:32:44.823 回答