如上所述，我有一个转换图，但我不知道如何找到它的语言，在我看来有很多可能性，但我一定是误解了。我的理解是，任何从初始状态到最终状态的词都被接受。当然，有很多不同的方法可以实现这一目标。阿布，阿布，阿布，阿巴布。据我了解，一种语言是所有可能单词的集合，但是如果有大量可能的单词，您如何找到该语言？我是大学一年级的学生，这是我家庭作业的一部分，但我不只是想让你为我做这件事，我想理解它——如果这没有意义/在错误的地方我提前道歉，谢谢。这是我的图表
问问题
1031 次
1 回答
2
一些常规语言是有限的——它们包含有限数量的字符串。当您拥有有限数量的事物时，这意味着您可以将它们全部计数并最终到达终点；如果它们是一种语言中的单词，您可以将它们全部写下来。用一种语言写下所有的单词是对一种语言进行广泛定义的一种方式。
但是 - 有些语言不是有限的。它们不包含任何您可以从头到尾数数或完全写下来的单词。如果您将所有自然数（1、2、...、100、...）视为十进制表示语言中的字符串，显然它们的数量并不有限。有无限多。你不能给出无限语言的广泛定义（除了可能通过省略号的暗示性使用，就像我在我的例子中所做的那样）。在这些情况下，您必须描述包含和/或排除的字符串，并依靠读者来推断任何特定情况的成员资格。
给出一个有限自动机是给出一个标准的一种完全合理的方法，根据该标准可以确定语言中的成员资格：让字符串通过自动机，看看它是否被接受。从这个意义上说，询问有限自动机的语言是什么可以被视为微不足道的：它接受使有限自动机处于接受状态的字符串语言。
描述语言的另一种方式是给出语法，或者对于正则语言，给出正则表达式。与您已经拥有的有限自动机相比，这些不一定是或多或少有用的描述语言的方法。
通常，在课程作业中，当您被要求描述有限自动机的语言时，您可能会被要求给出一个简单的英语定义 - 一个简单的字符串，并可能提供一些集合构建器符号。这就是我们将在这里尝试做的事情。
您的 NFA 在 q0 中循环，接受任意数量的a，直到它看到至少一个a。如果它在 ab之前看到 a a，它就会崩溃。之后，如果它看到至少一个b，它可以接受；它可以看到任意数量的b，但在最初运行 之后a，它再也不能a连续看到两个。机器仅在以 . 结尾时才接受b。
总而言之，这可能是对这种语言有益的简单英语描述：
所有以至少一个 开头、以
a结尾b且不包含 的aa第一个实例之后的子字符串的字符串b。
这种语言的正则表达式是aa*(bb*a)*.
于 2020-03-02T13:32:50.150 回答