问题标签 [finite-automata]

所以我正在从麻省理工学院的 OpenCourseWare 学习离散数学课程，我想知道......我看到了关系和图形之间的联系，但还不足以“拥有”它。我也在 SQL 中实现了一个简单的状态机，所以我很好地理解了图表，只是没有更严格地研究关系和集合是如何应用的。我是否应该遵循 Yegge 的思路，只浏览那些我不喜欢摸索的东西，等我学到更多东西后再回来？我希望能够更好地分析我每天创建的图形结构（听起来很有趣），并且我想确保我现在没有传递有价值的信息。

（编辑：我想更好地了解不同的集合和关系属性如何与图论等事物相关，以及基本图论如何与集合/关系相关。）

有什么好的资源可以让我了解更多信息吗？我正在使用 Rosen 的第 5 版离散数学及其应用，以防万一。

谢谢！

我们需要在C中实现一个简单的状态机。
标准的 switch 语句是最好的方法吗？
我们有一个当前状态（state）和一个转换触发器。

简单状态机有没有更好的方法

编辑：对于 C++，我认为 Boost Statechart库可能是要走的路。但是，它对C没有帮助。让我们专注于 C 用例。

是否可以编写一个匹配出现次数未知的嵌套模式的正则表达式？例如，当有未知数量的开/关大括号嵌套在外大括号内时，正则表达式是否可以匹配左大括号和右大括号？

例如：

应该匹配：

当我感恩节后回到学校时，我将参加 CS 理论课程，涵盖确定性和非确定性有限状态机、图灵机、下推自动机和其他一些内容等主题。但是，我还没有找到一个好的应用程序可以生成它们的可视化表示以及测试它们的工作方式（通过/失败等）。到目前为止我发现的最好的是jFlap，我发现它相当尴尬。

几乎所有使用的编程语言都是图灵完备的，虽然这提供了表示任何可计算算法的语言，但它也带来了自己的一系列问题。鉴于我编写的所有算法都打算停止，我希望能够用一种保证它们会停止的语言来表示它们。

词法分析时使用用于匹配字符串和有限状态机的正则表达式，但我想知道是否有一种更通用、更广泛的语言不是图灵完备的？

编辑：我应该澄清一下，通过“通用”我不一定希望能够用该语言编写所有停止算法（我认为这种语言不会存在）但我怀疑有共同的线程停止证明，可以推广以产生一种语言，其中所有算法都保证停止。

还有另一种方法可以解决这个问题——消除理论上无限内存的需要。一旦限制了机器允许的内存量，机器所处的状态数是有限且可数的，因此您可以确定算法是否会停止（通过不允许机器进入之前的状态） ）。

呃 - 问题所说的。这是我一直听说的事情，但我还没来得及调查它。

（更新）我可以查找定义......但为什么不（正如@erikson 指出的那样）深入了解您的真实经历和轶事。Community Wiki'd incase 可以帮助人们投票选出最有见地的答案。到目前为止有趣的阅读，谢谢！

我正在实施一个尽可能接近正式定义的 DFA 作为学习练习（和博客材料）

我计划使用一个 java.util.Set ，其中定义中涉及一个集合。

该定义涉及一组元组来定义合法的状态转换：(state,symbol) -> nextState。

我有一个带有成员 state、symbol 和 nextState 的 Transition 类。我已经实现了 equals() 和 hashCode() 来指示如果两个转换在状态和符号上匹配，则它们是相等的。然后我有一个 java.util.Set 的 Transition 实例。

在我的处理算法中，当我读取下一个符号时，我拥有当前状态。我预计使用这两个构建一个 Transition 对象，从 Set 中提取匹配的 Transition，然后它会告诉我下一个状态，我可以迭代。

但是 - 我看不到任何提取 java.util.Set 成员以供进一步使用的方法。我可以删除（对象 o），但这只是返回布尔值。

我究竟做错了什么？

我想写一些能画出有限状态自动机的东西。有谁知道与此相关的任何算法？

编辑：我应该提到我知道graphviz。我想构建自己的绘图程序/函数，所以我正在寻找的是一些更理论的东西/算法的伪代码。

我正在寻找对前端小部件代码进行去spaghttify 的方法。有人建议有限状态机是思考我在做什么的正确方法。我知道状态机范式几乎可以应用于任何问题。我想知道是否有一些经验丰富的 UI 程序员真正养成了这种习惯。

所以，问题是——你们中的任何一个 UI 程序员在你的工作中是否考虑到状态机？如果是这样，怎么做？

谢谢，-摩根

我正在为离散数学考试而学习，但我发现了这个我无法弄清楚的练习。

“为字母 Sigma = {0,1,2} 中的语言构建一个基本的有限自动机 (DFA,NFA,NFA-lambda)，其中字符串中元素的总和是偶数并且这个总和大于 3”

我尝试使用 Kleene 的定理连接两种语言，例如连接与此正则表达式相关的一种语言：

(00 U 11 U 22 U 02 U 20)*- 偶数元素

有了这个

(22 U 1111 U 222 U 2222)*- 总和大于 3 的那些

这有道理吗？？我认为我的正则表达式很松散。