问题标签 [nfa]

我正在用 C++ 实现 Brzozowski 算法。我理解这个算法没有问题，但我不知道如何用 C++ 编写整个东西。我知道它应该如何工作，但我没有任何编程技能。

有人可以帮我吗？我只需要一些建议，比如建立一个矩阵或从中获取信息。是否可以将数组放入矩阵中。也许有人知道如何反转算法的节点，或者有人有一些 C++ Brzozowski 算法的片段。

我正在寻找将正则表达式转换为 NFA。我知道我们需要将正则表达式转换为解析树，然后将其转换为 NFA。我正在使用java脚本。是否有任何 js 工具可以直接从给定的正则表达式生成解析树？

我也对解析树到 NFA 部分的转换感到困惑。

顾名思义，DFA 和 NFA 与正则表达式有什么关系？学习 DFA 和 NFA 是否有助于更好地理解正则表达式？

Python中是否有可用的模块将正则表达式转换为相应的NFA，或者我必须从头开始构建代码（通过将正则表达式从中缀转换为后缀，然后实现汤普森算法以获得相应的NFA）？

是否可以在 Python 中从转换表中获取 NFA 的状态图？

如果我在我的 nfa 中有这个过渡

对于字母 {a,b}

这是否意味着当 nfa 处于状态 q1 时将 b 或 a 作为输入读取时，存在从 q1 到 q2 的转换？或者在输入 a 和 b 上没有定义从 q1 到 q2 的转换

给定字母表{a, b}，我们将其定义为单词中出现的次数，对于. 证明下面的集合是有规律的。Na(w)awNb(w){a, b}

A = {xy | Na(x) = Nb(y)}

我很难弄清楚从哪里开始解决这个问题。任何信息将不胜感激。

L = w : (na(w) - nb(w)) mod 3 /= 0

我怎样才能找到这种语言的正则表达式？

我知道这意味着 As 的数量减去 B 的数量不能是 3 的倍数。所以 a - b 不能是 3、6、9、12 等。

但我仍然无法将它放入正则表达式。我首先尝试将其设为 DFA 或 NFA，但我也做不到。

任何帮助表示赞赏！

I have been looking out for some algorithm that has in input a regular expression or a string and that converts it into an NFA and then a DFA, and that would actually print out the transition table of the corresponding final DFA.

I'am thus wondering if there is already an algorithm or C or Python library that does that,or if you have suggestions of algorithms to use, that I could implement.

Thank you.

我在这个网站上发现了同样的问题，答案是描述如何将 NFA 转换为 regex 的 PDF。但这不起作用，因为这种方法有一些条件：

1. 有从初始状态到所有其他状态的转换，并且没有到初始状态的转换。
2. 有一个接受状态，只有转换进入它（并且没有传出转换）。
3. 接受状态不同于初始状态。
4. 除了初始状态和接受状态外，所有其他状态都通过转换连接到所有其他状态。特别是，每个状态都有到自身的转换。

在我的示例中，开始状态只是进入下一个状态，而不是所有状态（例如，q0 进入 q1 但没有进入 q2、q3），并且有到开始状态的转换。

那么将 NFA 转换为正则表达式的最简单方法是什么？我没有给出 NFA 示例，因为我没有一个特定的示例，这只是一个一般性问题，因为我遇到了这种 DFA，其中开始状态与所有状态不相关，并且是过渡到开始状态。

我想要一个通用算法来转换这种 NFA。

我目前正在编写一个正则表达式来匹配这样的字符串：

我希望正则表达式匹配每个 ' | 之间出现的每个字符集 '，但也匹配单独的表达式，例如：

我目前有这个，但我做错了消极的前瞻，我不确定如何继续。

Ps 我不太喜欢在这种情况下使用 .* ，但我想不出另一种匹配方式，因为 ' | 之间的字符 's 可以是单词字符、数字或介于两者之间的任何内容。

编辑：

我希望输出匹配看起来像这样：

正则表达式在第 1 行运行，输出：

正则表达式在第 2 行运行：

正则表达式在第 3 行运行：