finite-automata - 如何查找 NFA 的语言

Question

如上所述，我有一个转换图，但我不确定如何找到它的语言，在我看来有很多可能性，但我一定是在某种程度上误解了。我的理解是，任何从初始状态到最终状态的单词都会被接受。当然，有很多不同的方法可以实现这一目标。 aab，ab，abb，abbaab。按照我的理解，语言是所有可能的单词的集合，但是如果有大量可能的单词，你如何找到该语言呢？我是大学一年级学生，这是我作业的一部分，但我不仅仅是想让你帮我做，我想理解它 - 如果这没有意义/在错误的地方我提前道歉，谢谢。 Here's my graph

Answer 1

一些常规语言是有限的 - 它们包含有限数量的字符串。当你的东西数量有限时，这意味着你可以将它们全部数出来并最终得到结果；如果它们是某种语言中的单词，您可以将它们全部写下来。写下一种语言中的所有单词是给出一种语言的广泛定义的一种方式。

但是 - 有些语言不是有限的。它们不包含任何您可以从头到尾数出或完全写下来的单词数量。如果您将所有自然数(1、2、...、100、...)视为十进制表示语言中的字符串，那么显然它们的数量不是有限的。有无限多个。您无法给出无限语言的广泛定义(除非可能通过暗示性使用省略号，正如我在示例中所做的那样)。在这些情况下，您必须描述包含和/或排除的字符串，并依靠读者来推断任何特定情况的成员资格。

给出一个有限自动机是给出一个标准的一种完全合理的方式，根据该标准可以确定语言中的成员资格:通过自动机运行字符串并查看它是否被接受。从这个意义上说，询问有限自动机的语言是什么可以被视为微不足道:它接受使有限自动机处于接受状态的字符串语言。

描述语言的另一种方法是给出语法，或者对于正则语言，给出正则表达式。这些不一定比您已有的有限自动机更有用或更少描述语言。

通常，在类(class)作业中，当您被要求描述有限自动机的语言时，您可能会被要求给出一个简单的英语语言定义 - 一个简单的 - 字符串，并可能提供一些集合 -构建器符号。这就是我们将在这里尝试做的事情。

您的 NFA 在 q0 中循环，接受任意数量的 a，直到它至少看到一个 a。如果它在 a 之前看到 b，则会崩溃。之后，如果它看到至少一个b，它就可以接受；它可以看到任意数量的 b，但在首次运行 a 后，它再也无法连续看到两个 a。机器仅接受以 b 结尾的内容。

综合起来，这可能是适合该语言的简单英语描述:

All strings that begin with at least one a, which end with b and which do not contain the substring aa after the first instance of b.

该语言的正则表达式为 aa*(bb*a)*。