问题标签 [finite-automata]

这个问题可能听起来陈词滥调，但我在这里遇到了情况。

我正在尝试实现一个有限状态自动机来解析 C 中的某个字符串。当我开始编写代码时，我意识到如果我使用标签来标记不同的状态并使用 goto 从一个状态跳转到另一个视情况而定。

在这种情况下，使用标准中断和标志变量非常麻烦，并且难以跟踪状态。

什么方法更好？最重要的是，我担心这会给我的老板留下不好的印象，因为我正在实习。

你更倾向哪个？

我想在java中制作一个有限自动机；使用向量或集合更有效吗？

(ab+ba)*接受所有零个或多个“a”，后跟零个或多个“b”，以及零个或多个“b”，后跟零个或多个“a”。这个 RE 的拒绝状态是什么？

想想那些不被(ab+ba)*.

大多数语言都允许固定长度或有限长度的后视。一个值得注意的例外是 .NET，它允许使用 * 运算符。

但是，.NET 正则表达式已经可以使用命名捕获识别平衡括号，这不是常规语言。正则表达式在后视中是否仍然是带有 * 的常规表达式？对 * 以外的子表达式的扩展答案（例如，额外的环视！）也将不胜感激。

tl;dr：正则表达式是否与 * 保持一致？

众所周知，如何从常规语言的 NFA 到最小 DFA。但是，DFA 可能具有成倍增加的状态数。

我需要的是一种减少 NFA 的方法，再次给出 NFA 但状态数量较少。我不需要结果是确定性的，但我希望它尽可能小，同时保留公认的语言（也许不是绝对最优，但越小越好）。

这个问题的最佳算法是什么？或者也许不是“最好的”，但至少是“最容易以非糟糕的效率实施”？或者问题是否有一个众所周知的名称，以便我自己可以找到好的信息来源？

我已经在一个项目上工作了一个月左右，以便在 javascript 中开发一个 XML 验证器 (XSD)。我已经非常接近但不断遇到问题。

我唯一做得好的是将模式结构规范化为我存储在 DOM 中的 FSA。我尝试了几种方法来针对 FSA 验证我的 xml 结构，但每次都失败了。

验证器用于运行客户端所见即所得 XML 编辑器，因此它必须满足以下要求

• 必须高效（即使使用复杂的模型也需要 < 15ms 来验证元素子节点模式）
• 必须公开一个验证后架构信息集 (PSVI)，可以查询该信息集以确定可以在各个点从文档中插入/删除哪些元素，并且仍然保持文档有效。
• 必须能够验证 xml 子节点结构，如果无效，则返回预期的内容或未预期的内容。

-- 更多信息 考虑以下示例--
首先，我将模式结构转换为通用 FSA 表示，以规范化 xs:group 和 xs:import 等与命名空间相关的内容。例如考虑：

将转换为类似的广义结构：

我通过 XQuery 和 XSLT 在服务器端完成这一切。

我第一次尝试构建验证器是在 javascript 中使用递归函数。在此过程中，如果我发现可能存在的内容，我会将其添加到全局 PSVI 中，表明它可以添加到层次结构中的指定点。

我的第二次尝试是迭代的，而且速度更快，但两者都遇到了同样的问题。

这两种方法都可以正确验证简单的内容模型，但是一旦模型变得更加复杂和非常嵌套，它们就会失败。

我在想我是从完全错误的方向来解决这个问题的。根据我的阅读，大多数 FSA 都是通过将状态推送到堆栈来处理的，但我不确定在我的情况下如何做到这一点。

我需要关于以下问题的建议：

1. 状态机在这里是正确的解决方案吗，它会实现顶部所述的目标吗？
2. 如果使用状态机将模式结构转换为 DFA 的最佳方法是什么？汤普森算法？我是否需要优化 DFA 才能使其正常工作。
3. 用javascript实现这一切的最佳方式（或最有效的方式）是什么（注意优化和预处理可以在服务器上完成）

谢谢，

凯西

附加编辑：

我一直在看这里的教程：http: //www.codeproject.com/KB/recipes/OwnRegExpressionsParser.aspx专注于正则表达式。它似乎与我需要的非常相似，但专注于为正则表达式构建解析器。这带来了一些有趣的想法。

我认为 xml 架构分解为只有几个运算符：

序列 -> 连接
选择 -> 联合
minOccurs/maxOccurs - 可能需要的不仅仅是 Kleene Closure，不完全确定表示此运算符的最佳方式。

问这么简单的问题让我感觉很糟糕，但我无法终生解决这个问题。我需要构建一个基于某些语言的 NFA，我唯一想不通的是这个：

请注意，我不是在寻求有关 FSM 的任何帮助，而只是对语言所代表的内容进行一些澄清。大多数其他语言都以更易于理解的方式呈现给我：

我认为这只是一个正则表达式，在仔细阅读了正则表达式备忘单之后，我唯一的猜测是它匹配组100 次或更多次，但这显然不正确，因为一切都会匹配。

任何帮助是极大的赞赏。

我有一个 DFA 问题（行列式有限自动机）。我们正在使用 JFLAP 来构建自动机。我想不出这个问题来挽救我的生命！这里是

“DFA 可以识别具有偶数个零和奇数个 1 的所有字符串的语言。”

所以字母表是 {0,1} 并且只使用 0,1。所以我需要建立一个自动机来识别偶数个零和奇数个零。

两个 DFA（Deterministic Finite Automaton 或 Deterministic Fininte-State Machines - 从这里开始称为 DFA）在集合 DFA 1 上定义：L1 = {Q1，E，D1，s1，F} DFA 2：L2 = {Q2， E, D2, s2, F}

Q 是状态列表。例如 1、2、3、4 或 a、b、c、d

E是语言Ex。0, 1

D 是转移集 Ex。{(a,0,b)} 状态 a 在 a 0 上进入 b

s 是起始状态

F是最终状态

您将如何取两个 DFA L1 和 L2 的异或

下午好，

有谁知道 .NET 中的 Levenshtein DFA（确定性有限自动机）的“开箱即用”实现（或易于翻译）？我有一个非常大的字典，其中包含超过 160000 个不同的单词，并且我想给定一个初始单词w ，以有效的方式在 Levenshtein 距离最多 2 个w找到所有已知单词。

当然，有一个函数可以计算给定单词的一个编辑距离处的所有可能的编辑，并将其再次应用于这些编辑中的每一个，可以解决问题（并且以一种非常简单的方式）。问题是效率 --- 给定一个 7 个字母的单词，这已经需要 1 秒多的时间才能完成，我需要更高效的东西---如果可能的话，就像 Levenshtein DFA 一样，一个需要 O( | w| ) 步骤。

编辑：我知道我可以通过一点学习来构建自己的解决方法，但目前我无法阅读 Schulz 和 Mihov 的 60 页长的文章。

非常感谢你。