(a+b)?c 的 NFA

Question

我需要正则表达式的 NFA

(a+b)?c

据我了解，它应该包含从零节点到最后一个节点之前的 epsilon（例如匹配字符串 "c"）。

为了检查我的 NFA，我使用“Regular Expression to NFA Visializaton web service”，但是此服务上我的正则表达式的图形不包含来自零节点的 epsilon。

是服务有问题，还是我理解有误？

谢谢！

Answer 1

似乎是一个错误。如果我尝试 (aa*b)?c 这应该是相同的语言，NFA 看起来非常不同（并且正确）。另外，当我尝试使用我自己开发的自动机库时，我得到了这个：

./fatool --in 're:^(a+b)?c$' --out dot:- | dot -Gdpi=70 -Tpng -onfa.png /dev/stdin

有兴趣的图书馆：https://github.com/wader/libfa

Answer 2

对我来说这似乎是一个错误。试图减少问题，a+? 也失败了。

还有另一个错误 a|，它应该等同于 a?，导致服务器出现 HTTP 错误 500。

唱反调，他们可能会忽略某些情况，因为它们在常规语言下没有关闭。如果他们接受对表达式语言的一些 non-regular 扩展，这将是可能的。

也许您的示例并不是真正的常规语言。如果是这种情况，那么该工具可能会按预期执行。也就是说，如果给定一个表示正则语言的正则表达式，那么它会生成一个识别该正则语言的 NFA 和 DFA。然而，反过来可能不成立。

为了增加此回复的分量，我将证明您的示例确实是一种常规语言。

首先我们定义什么是常规语言。空 ε 和字母表的任何符号都是常规语言。如果 x 和 y 是常规语言，则：连接 x·y、选择 x|y 和重复 x* 是常规语言。

对于符号，从低到高的优先级是：|、·、*。此外，我们添加了通常的括号，它们具有最高的优先级。 | 和 · 都是关联的，所以例如 (a·b)·c 和 a·(b·c) 将写成 a·b·c.

现在可以通过构造示例来证明该示例是一门正则语言。假设字母表包含 'a'、'b' 和 'c'。为了简洁起见，这个推导树没有标明所使用的规则，但是很容易推断出来。

    --
    a
--  --
a   a*
-----   --
 a·a*   b
----------   --
  a·a*·b     ε
 --------------   --
   (a·a*·b)|ε     c
 ------------------- 
    ((a·a*·b)|ε)·c

可以假定这些定义。

x+ ≡ x·x*
x? ≡ x|ε
xy ≡ x·y

然后使用定义可以得到例子。 + 和 ? 与 * 具有相同的优先级。

((a·a*·b)|ε)·c
((a+·b)|ε)·c
((a+b)|ε)·c
(a+b)?·c
(a+b)?c

这不是理解常规语言的唯一方式。另外，我还没有定义在构造语言中实际是什么词，所以与你的例子的等价性被认为是理所当然的——根据使用的约定，我希望这种等价性足够明显。

(a+b)?c 的 NFA

NFA for (a+b)?c

regex

nfa