regex - 反向应用的正则表达式会产生相同的匹配吗？

Question

假设我们有一些文本和匹配它的正则表达式。问题:如果我向后对文本应用相同的表达式(从最后一个字母到第一个字母)，它仍然匹配吗？

正则表达式 -----> 文本

xereg --?--> txet

在实践中似乎行得通，问题在于理论对一般情况的看法。

Answer 1

如果您使用 Kleene 星号则不会 - 如果您反转正则表达式，您将得到无效的正则表达式或匹配不同模式的正则表达式:

• ab* -> *ba(语法无效)
• a*b -> b*a(第一个匹配aaab但不匹配abbb，而第二个匹配 bbba 但不匹配 baaa)

另一方面，我很确定可以设计一种算法，在给定正则表达式的情况下，生成与反向字符串匹配的正则表达式。以下递归算法应该有效(如果 r 是正则表达式，rev(r) 表示匹配反转字符串的正则表达式):

• 如果 r 是单个符号 x，则 rev(r) = x。
• 如果 r 是联合 A|B，则 rev(r) = rev(A)|rev(B)。
• 如果 r 是一个串联 AB，则 rev(r) = rev(B)rev(A)。
• 如果 r 是 Kleene 星 A*，则 rev(r) = rev(A)*。