regex - 一种语言在 a,b,c 上的正式正则表达式，使得 a 从不与 b 相邻

Question

我正在尝试为带有字母 a、b、c 的语言编写正则表达式查询，以使 a 永远不会与 b 相邻。

是否可以仅使用交替（加）、连接和重复（乘）运算符来完成？

L = w 属于 {a,b,c}* 使得 a 永远不会与 b 相邻

Answer 1

（让我们看看我是否记得足够多的形式语言理论。）

这样的正则表达式可以在 DFA 的帮助下构建，如下所示：

A = aA + cC + F      // only a or c can follow a
B = bB + cC + F      // only b or c can follow b
C = cC + aA + bB + F // any char can follow c

其中A和是表示当 和 分别是前一个字符时的B状态的状态。由于任何角色都可以跟随，我们可以创建我们的起始状态。是最终的结束状态（字符串结束）。CabccCF

可以将此 DFA 转换为如下正则表达式：

A = a*(cC+F) // eliminate recursion
B = b*(cC+F) // eliminate recursion

C = cC + aA + bB + F
  = cC + aa*(cC+F) + bb*(cC+F) + F       // substitute A and B
  = (c + aa*c + bb*c)C + aa*F + bb*F + F // regroup
  = (c + aa*c + bb*c)*(aa*F + bb*F + F)  // eliminate recursion
  = (c + aa*c + bb*c)*(aa* + bb* + e)F   // regroup

所以表达式是：

(c + aa*c + bb*c)*(aa* + bb* + e) // e being the empty/null string

或以非正式的正则表达式格式：

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

可以缩短为：

(a+c|b*c)*(a*|b*)