问题标签 [dfa]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
f# - 用 F# 编写的有限自动机库
您能否推荐一个用 F# 编写的开源库，它为 FA 构造和基本算法（NFA 到 DFA 转换、FA 最小化......）提供通用类型？
regex - 将字符集转换为 nfa/dfa 的高效算法
我目前正在研究扫描仪生成器。生成器已经可以正常工作了。但是当使用字符类时，算法变得非常慢。
扫描仪生成器为 UTF8 编码文件生成扫描仪。应该支持全范围的字符（0x000000 到 0x10ffff）。
如果我使用大型字符集，例如任何运算符 '.' 或 unicode 属性 {L}，nfa（以及 dfa）包含很多状态（> 10000）。因此，将 nfa 转换为 dfa 并创建最小 dfa 需要很长时间（即使输出的最小 dfa 仅包含几个状态）。
这是我当前创建 nfa 的字符集部分的实现。
有谁知道如何更有效地实现该功能以仅创建必要的状态？
编辑：
更具体地说，我需要一个函数，例如：
将字符 (int) 转换为 UTF8 编码 byte[] 的辅助函数定义为：
xml - 解析器与词法分析器和 XML
我现在正在阅读有关编译器和解析器架构的信息，我想知道一件事……当您拥有 XML、XHTML、HTML 或任何基于 SGML 的语言时，词法分析器在这里的作用是什么，令牌是什么？
我读过令牌就像为lexer解析准备的单词。虽然我在查找 C、C++、Pascal 等语言的标记方面没有问题，其中有关键字、名称、文字和其他由空格分隔的类似单词的字符串，但使用 XML 我有问题，因为没有没有任何话！它只是与标记（标签）交错的纯文本。
我心想，这些标签和纯文本片段可能是标记，类似于：[TXT][TAG][TAG][TXT][TAG][TXT][TAG][TAG][TXT].... 这是相当合理的，因为 SGML 不关心标记分隔符内的内容，<并且>（好吧，它在找到?或!作为下一个字符时识别特殊处理指令和定义；注释也属于该组），并且 SGML 标记器可以成为 XML/HTML/XHTML 解析器的基础。
但是后来我意识到，<作为其他语法的一部分，标记中可以填充字符：属性值：-/ 即使将<字符放在属性值中并不是一个好主意（最好使用<它），许多浏览器和编辑器处理它并将它们<视为属性值的一部分，而不是标签分隔符。
它使事情变得有点复杂，因为我看不到通过词法分析器中的简单确定性有限自动机 (DFA) 来识别这样的标记的方法。当自动机在标签内时，它看起来需要一个单独的上下文，当它遇到属性值时需要另一个上下文。我认为这需要一堆状态/上下文，所以 DFA 可能无法处理。我对吗？
你有什么看法？从标签（标记）和纯文本制作标记是否很好？
在这里：http://www.antlr.org/wiki/display/ANTLR3/Parsing+XML
使用了某种不同的技术：它们将<and >（以及</and />）视为单独的标记，并在它们GENERIC_ID用作标记的标签内等.他们通常将大部分工作转移到解析器。但是他们还必须更改标记器的上下文：他们在纯文本中使用不同的上下文，并且在标记中使用不同的上下文（但我认为他们忘记了属性值上下文，因为第一次出现 of>将在他们的词法分析器中结束标记）。
那么解析类 SGML 语言的最佳方法是什么？词法分析器真的在那里使用吗？如果是，哪些字符串构成了标记？
finite-automata - 行列式有限自动机 (JFLAP)
我有一个 DFA 问题（行列式有限自动机）。我们正在使用 JFLAP 来构建自动机。我想不出这个问题来挽救我的生命！这里是
“DFA 可以识别具有偶数个零和奇数个 1 的所有字符串的语言。”
所以字母表是 {0,1} 并且只使用 0,1。所以我需要建立一个自动机来识别偶数个零和奇数个零。
math - 从两个确定性有限自动机创建异或（确定性有限状态机）
两个 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 的异或
java - 表示 DFA 的数据结构
我想知道，代表 DFA 的最佳数据结构是什么？
我正在考虑将正则表达式转换为 DFA，并将此特定功能作为 Java 中的库。
主要的是，正则表达式中的每个实体都带有一组值，而不是像 "car" 这样的单个字符串值。在我的例子中，每个实体都会带有许多属性，例如 {car, Honda, 4x4,轿车, ... }（虽然我不是在搜索汽车，但这只是一个示例。）
有什么建议么？
deterministic - 如果一种语言 (L) 被 n-state NFA 识别，那么它是否也可以被不超过 2^n 个状态的 DFA 识别？
我是这么想的，因为上限是 2^n，并且鉴于它们都是有限机器，n 状态 NFA 和具有 2^n 或更少状态的 DFA 的交集将是有效的。
我在这里错了吗？
fsm - 描述 DFA 或 NFA 的语法
是否存在用于描述 NFA 或 DFA 的转换表的标准语法？
regex - DFA 与 NFA 引擎：它们的功能和限制有何不同？
我正在寻找关于 DFA 与 NFA 引擎之间差异的非技术解释，基于它们的功能和限制。
dfa - 具有可变转换条件的 NFA/DFA
晚安，
假设我有一个实现 NFA/DFA 的类，它的转换存储在 .NET Dictionary 结构中，它接受一个输入单词并识别一组可从输入中以某种方式派生的单词。此外，假设自动机是一个通用模板，它可以应用于相同长度的不同单词，只需重新标记过渡字符。在 Dictionary 中对转换函数进行编码以便在运行时根据输入单词的字符重新标记转换函数的最佳方法是什么？
非常感谢你。