问题标签 [automata]
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.
java - 适用于 JFLAP 的 IP 验证正则表达式
我注意到我们程序员在我们的程序中使用的正则表达式用于诸如
- 电子邮件地址验证
- 知识产权验证
- ...
与Automata中使用的那些正则表达式有点不同（如果我没记错的话）
顺便说一句，我想设计一个 NFA 并最终设计一个用于 IP 验证的 DFA。我发现了很多正则表达式，例如以下一个：
但我无法使用 JFLAP 将其转换为 NFA 或 DFA。
我应该怎么办？
finite-automata - 对于给定的正确输入字符串，如何纠正稍微不正确的 DFA？
我写了一个可以生成 DFA 的程序。但是 DFA 有点不正确。也就是说，有时他们不能接受正确的字符串。
我的问题是：是否有任何算法可以纠正 DFA，以便它们可以接受给定的正确字符串？
更正式地说，
假设 DFA D不接受字符串str。
需要一个算法A , st D' = A( D, str)并且D'接受str
automata - 理解形式语言中的 Σ* 和 Σ
如果我有Σ={a}，有什么话Σ*？
Σ*= {a,aa,aaa,aaaa.....}?
谢谢
context-free-grammar - L* 和 Σ* 之间的差异
有人可以解释和之间的确切区别Σ*，语言L*在哪里，
L语言Σ的字母在L哪里？
谢谢
algorithm - 使用 LRS 数组增强的因子 oracle 查找多个字符串的最长公共子字符串
我们可以使用带有后缀链接的因子-oracle（此处为论文）来计算多个字符串的最长公共子字符串吗？这里，子字符串表示原始字符串的任何部分。例如“abc”是“ffabcgg”的子字符串，而“abg”不是。
我找到了一种方法来计算两个字符串的最大长度公共子字符串s1和s2. 它通过使用不在其中的字符连接两个字符串来工作，例如'$'。s然后对于长度为 的连接字符串的每个前缀i >= |s1| + 2，我们计算其 LRS（最长重复后缀）长度lrs[i]和sp[i]（其 LRS 第一次出现的结束位置）。最后，答案是
我已经编写了一个使用这种方法的 C++ 程序，它可以在我的笔记本电脑上|s1|+|s2| <= 200000使用因子 oracle 在 200 毫秒内解决问题。
我知道使用 suffix-array 和 suffix-tree 可以高效地解决这两个问题，但是我想知道是否有使用因子 oracle 的方法来解决它。我对此感兴趣是因为因子 oracle 很容易构造（用 30 行 C++，suffix-array 需要大约 60，而 suffix-tree 需要 150），并且它比 suffix-array 和 suffix-tree 运行得更快。
您可以在此 OnlineJudge中测试您的第一个问题的方法，并在此处测试第二个问题。
java - 检查一个字符串是否有四个连续的字母以升序或降序排列
美好的一天堆栈溢出。
我是使用正则表达式的菜鸟，这是我的问题 - 如果密码包含 4 个连续字符，我需要检查它。到目前为止，我刚刚介绍的是关于数字的。这是我的正则表达式：
升序数字 - ^。?(?:0123|1234|2345|3456|4567|5678|6789)。$
递减数字 - ^. ?(?:9876|8765|7654|6543|5432|4321|3210)。$
这仅适用于数字。我知道这在正则表达式中已经是一种矫枉过正，所以我不想用字母来做。如果我这样做，那就太矫枉过正了。
abcdblah //因为 abcd 而为真
helobcde //true 因为 bcde
dcbablah //真正的因为 dcba
heloedcb //true 因为 edcb
任何帮助将不胜感激。感谢堆栈溢出。
dfa - Hopcroft 的 DFA 最小化算法是否有公开可用的实现？
同上。Java 或 C# 是最好的，但任何命令式语言都可以。
regex - 自动机和正则表达式理论工具
早在 2000 年，当我还是一名学生时，我参加了自动机理论课程。在本课程的练习中，我们基本上重新编写了一个名为 Grail ( http://www.csd.uwo.ca/Research/grail/ ) 的 unix 命令行工具。Grail 允许您读取带有正则表达式或确定性/非确定性有限状态机的文件，并对它们应用典型的理论操作：最小化 FSM、检查空虚、反转、FSM 的乘积、FSM 到 RegEx 和 RegEx 到 FSM、应用输入字符串和模拟机器等等。
Grail 似乎可用，但显然自 2002 年以来尚未开发。因此我的问题是：有人知道仍在积极开发中的类似工具吗？（即现代圣杯？）今天的课堂使用什么？
我正在寻找的是一个命令行工具，它从标准输入读取 FSM 或 RegExes，应用操作，并将结果输出到标准输出，Unix 方式，以便您可以创建自己的管道。简单的 FSM 和 RegEx 就足够了，所以像下推自动机或 Büchi 自动机这样的东西并不是真正需要的。
如果没有命令行工具，是否有好的库或图形工具？
c++ - 调试或映射出大型状态机？
我正在尝试调试一段代码，它主要是一个简单的 16 状态状态机，尽管在某些情况下转换不是很简单（状态更改操作的数据是几个 C++ 中大约 200 字节的数据类）。
我们发现这台机器比预期的要早得多地进入“最终”状态。由于我对代码还不是很熟悉，我希望我可以尝试找出不同的状态和转换，从而使我更容易快速识别和调试不同的转换路径。
是否有任何有用的工具或技术可以映射出这样的状态机？
值得注意的是，我是从逆向工程的角度来做这件事的，所以我没有可用的系统规划文档。
context-free-grammar - 从给定语言构建上下文无关语法
我需要帮助为给定语言构建 CFG。
L = { x ∈ {a, b}* | x != x reversed }，换句话说，L是 中所有回文的补集L。
我对如何解决这类问题而不是具体的解决方案更感兴趣。