正则表达式可以用来识别任何上下文无关语言吗？

Can regex be used to recognize any Context Free Language?

我知道正则表达式包可以识别比常规语言更广泛的语言集，但是 中递归正则表达式的使用让我想知道是否有可能识别 任何 使用正则表达式的上下文无关语言，如果没有，有人可以提供一个反例吗？

基本上这个答案来自this很棒的博客post。

所以简短的回答是具有递归扩展的正则表达式可以识别任何上下文无关语法。

为了展示这一点，我们的想法是展示一种从上下文无关语法构造正则表达式的方法。

(?<name> ...) 定义了一个正则表达式模式，以后可以在 (?&name).

中重复使用

任何上下文无关文法都可以写成以下形式的一组规则：

  • A -> BC
  • A -> a

如果我们可以将这些规则写成正则表达式，则正则表达式可以识别任何上下文无关语言。这里唯一有趣的规则是第一个。

首先，如果规则是左递归的，我们需要将其重写为右递归规则，因为正则表达式只支持右递归。这种重写总是可能的。现在我们可以将所有这些规则写成如下：

A -> BC
A -> DE
(?<A>(?&B)(?&C)|(?&D)(?&E))

这样就可以定义任意的CFG规则，所以我们只需要全部定义好，然后匹配初始规则即可。

(?(DEFINE)define rules here)^(?&initial)$

这里(?(DEFINE)...)声明的是没有匹配的规则，initial指的是文法的初始规则

好久没听CS理论课了，有错误请指正:)