1

我知道根据左分布规则，这个正则表达式： A ( B + C )

可以这样写：AB+AC

我的问题是下一个。在这个例子中可以使用左分配规则吗： A ( B + C* )

这样我就可以得到： AB + A(C*)

或者我得到这样的东西：AB + AC *

谢谢

4

3 回答 3

5

AB + A(C*)绝对正确（并且AB + AC*几乎可以肯定也是正确的，取决于 的优先级*）。

有问题的正则表达式是A ( B + C* )⇔ A ( B + (C*) )。如果我们使用c=C*作为替代，我们可以将原始的正则表达式写为A ( B + c )，现在很明显我们可以使用左分配规则。一口气完成所有步骤：

A ( B + C* ) <=> A ( B + (C*) ) <=> AB + A(C*) <=> AB + AC*

（出于教学目的，这里的工作比必要的要多，我用<=>的是“等同于”的意思。）

我们也可以只看有问题的正则表达式匹配什么（这不是证明，但它很好地证明了它们是等价的）：

  • A(B + C*)匹配A后跟单个B或任意数量的Cseg AB, A, AC, ACC, ACCC...
  • AB + A(C*)匹配任意数量AB的seg , , , , ...ACABAACACCACCC

这些是完全一样的。

于 2012-05-03T10:07:43.173 回答
1

据我所知A(B+C*)是不一样的AB + A(C*)。第一个表达式匹配 ABBBBBBBBBBBBB 或 ABBBBBBBBBBBC 等字符串 第二个表达式匹配 ABBBBBBBBBBBA 或 ABBBBBBBBBBBACCCCCCCCCCC 等字符串

于 2012-05-03T09:52:33.073 回答
0

AB + A(C*) 这个是正确的，因为

C* 表示 0 或更多（你有 0 或 C 的倍数） C+ 表示 1 或更多（至少一个 c 或多个）

于 2012-05-03T09:35:16.187 回答