0

对于 Σ = {a,b,c,d,e,...,z}，考虑单词 w 的集合 L，使得 w 的最后一个符号之前没有出现过。例如，单词 apple、google、k 和 ε 在 L 中，但单词土豆和营养不在 L 中。假设我们要为这种语言构造一个 DFA。它将有多少个州（最少）？简明扼要地描述 DFA：不要试图画出它，而是使用合适的数学符号来解释它的正式定义（例如状态和转换）。

我不需要完整的定义，只是一个关于它将有多少个状态以及为什么的开始。从那里我有信心我能弄清楚。

4

1 回答 1

0

一些提示：

  • 对于 Σ 的每个可能子集，您将需要一个状态，以便您可以跟踪到目前为止您看到的字符。

  • 对于 Σ 的每个子集，您将需要另一个状态来表示“这组字符，其中最后一个读取的字符恰好在该组中”。

我将把其余的细节留给你，你必须考虑如何正式证明这是正确的。

希望这可以帮助！

于 2014-01-25T01:45:07.510 回答