构建有限状态机

Question

在构造表示给定语言的有限状态机时，需要考虑的主要问题是什么？我知道有限状态机将字符串作为输入，并且随着字符串的每个元素被读取，机器状态会发生变化，直到达到 EOF。如果字符串被完全读取后，机器处于最终状态之一，则字符串被接受。我不明白的是在构建FSA时需要考虑什么（除了它应该接受的字符串，以及每个转换函数的定义。）

Answer 1

您需要考虑的一件事是州的数量。有许多等效的方法来定义机器，但通常首选较少的状态，因为可以用较少的复杂性和 space 实现相同的结果。

计算自动机的表示需要 space 与状态数成比例，因此 optimizing 通过状态减少来实现空间复杂性是可取或必要的。