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并且C是代表国家时的状态a,b并c分别为前一个字符.由于任何角色可以遵循,c我们可以使C我们的开始状态.F是最终的结束状态(字符串的结尾).

此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*)