1

我正在做一个处理状态机的家庭作业。我了解它们的运作方式，但是我不了解这个特定问题的几个方面。

Let L be the set of strings over {a,b} ending with the substring abba.
a. Build a DFA that accepts L.
b. Build an NFA with 6 transitions that accepts L.

如何将 L 合并到状态机中？我完全迷失了b部分，但我觉得一旦我理解了a部分，b应该不会太难。

4

2 回答 2

2

让我们备份一下。按照惯例，“L”用于定义“语言”——在这种情况下，一组（可能是无限的）符合某些定义的字符串。在玩有限自动机时，您会关心机器“接受”哪些字符串以及“拒绝”哪些字符串，通常您希望接受给定语言中的所有字符串并拒绝那些不在其中的字符串（另一种看待问题的方式是，您可以将语言定义为机器接受的所有字符串的集合——它们是等价的）。

第一个问题是构建一个接受 L 的 DFA 的练习——也就是说，给定任何以“aaba”结尾的字符串，它接受并给定不以“abba”结尾的字符串，它拒绝。您的困惑似乎来自于认为 L 不知何故是您机器的“一部分”；充其量您将 L 的描述编码到您的机器中。

第二个问题是要求您对 NFA 做同样的事情，但附加限制是它只有 6 个转换。

于 2012-06-23T01:32:13.233 回答
0

让我试试这个：

Node 0:
a -> node 1   <-- This means, "if the next character is a, then go to node 1"
b -> node 0
END -> error
Node 1:
a -> node 1
b -> node 2
END -> error
Node 2:
a -> node 1
b -> node 3
END -> error
Node 3:
a -> node 4
b -> node 0
END -> error
Node 4:
END -> Success!
a -> node 1
b -> node 0

我相信应该这样做。每个节点都有 3 个可能的箭头，用于 a、b 或字符串结尾 (END)。作为“abbaEND”一部分的每个输入都会导致下一个节点并最终成功，并且不属于“abbaEND”的每个输入都会将您带回适当的节点。基本上，如果它是 a，它会将其视为另一个“abba”块的开始，如果它是 ab，则假定“abba”接下来会出现。提前结束是失败的。那应该是您的 DFA 地图。

因此，使用 a 和 b 的任何字符串作为输入......这个 DFA 应该只以 Success 结尾！如果字符串以“abba”结尾，并且对于任何其他字符串都应该以错误结尾。

于 2012-06-23T01:41:14.157 回答