在构造表示给定语言的有限状态机时,需要考虑的主要问题是什么?我知道有限状态机将字符串作为输入,并且当读取字符串的每个元素时,机器状态会发生变化,直到到达EOF。如果字符串被完全读取,则机器处于最终状态之一,该字符串被接受。我不理解的是,在构造FSA时需要考虑什么(除了它应该接受的字符串和每个转换函数的定义之外)。
发布于 2018-06-10 03:44:31
您需要考虑的一件事是状态的数量。有许多等效的方法来定义机器,但通常首选较少的状态数量,因为以较少的复杂性和空间实现相同的结果。
计算自动机的表示需要与状态数成正比的空间,因此通过状态约简来降低空间复杂度( optimizing )是可取的或必要的。
https://stackoverflow.com/questions/50777558
复制相似问题