computer-science - 有向图与有限状态机

Question

Closed. This question needs to be more focused。它当前不接受答案。












想改善这个问题吗？更新问题，使其仅通过 editing this post专注于一个问题。

3年前关闭。



Improve this question





在计算机科学/软件工程中，有向图和有限状态机有什么区别？

最佳答案

有向图是以下项的有序对：


一组节点N和
N上的binary relation。


Labeled directed graphs在节点和边缘上还具有注释（标记功能）。这些是语法构造，即归因于这些注释的语义不是标签本身的一部分，而是取决于上下文的归因于我们的解释。 （另请参见multidigraph）。

换能器的定义在this answer中讨论。它是一个元组，它包含节点，边，输入字母，输出字母，一组初始状态和标签功能：具有输入字母的边，具有状态（摩尔）或具有输出字母的边（Mealy）的元组。

因此，有向图实质上是一种数据结构，无法表示有限状态机。相反，带标记的有向图是可以表示有限状态机的数据结构（尽管在代数上它们是不同的结构-尽管这更多地是技术性的）。

顺便说一句，“初始状态集”可以等效地通过将状态标记为初始状态或不初始状态来描述，因此配备有足够数量的标记功能的图足以描述有限状态机。

关于computer-science - 有向图与有限状态机，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10657304/

上一篇：R-创建交易对方频率矩阵

下一篇：nunit - 如何设计一个 NUnit 理论？

相关文章：

algorithm - 数据结构、算法、基础计算机科学、在线资源的比较

比较(目标)C 中的枚举数组

algorithm - 在有向循环图中找到从源 s 到目标 f 的最长路径。假设不存在正权重循环

java - 如何让数字保持在0-359之间？假设如果超过 1 到 360，它将重新开始为 0

algorithm - 从图表创建 "pairing"？

design-patterns - 在游戏开发中处理状态和状态变化的好技术是什么？

go - 如何从对象的构造函数中提取该变量的初始化？

r - 在 R 中使用 iGraph 获取路径的权重

algorithm - 确定有向图是否单连通的最有效方法是什么？

arrays - 数据结构的选择

Answer 1

有向图是以下项的有序对：


一组节点N和
N上的binary relation。


Labeled directed graphs在节点和边缘上还具有注释（标记功能）。这些是语法构造，即归因于这些注释的语义不是标签本身的一部分，而是取决于上下文的归因于我们的解释。 （另请参见multidigraph）。

换能器的定义在this answer中讨论。它是一个元组，它包含节点，边，输入字母，输出字母，一组初始状态和标签功能：具有输入字母的边，具有状态（摩尔）或具有输出字母的边（Mealy）的元组。

因此，有向图实质上是一种数据结构，无法表示有限状态机。相反，带标记的有向图是可以表示有限状态机的数据结构（尽管在代数上它们是不同的结构-尽管这更多地是技术性的）。

顺便说一句，“初始状态集”可以等效地通过将状态标记为初始状态或不初始状态来描述，因此配备有足够数量的标记功能的图足以描述有限状态机。