概括了UNIX风格的正则表达式的抽取引理

Question

大多数UNIX正则表达式有,除了一般的**,+,?*运营商反斜杠算哪里\1,\2,...的比赛无论是在过去的括号,因此,例如*L=(a*)b\1*(非正规)语言相匹配*a^n b a^n*.

一方面,这似乎非常强大,因为您可以创建(a*)b\1b\1匹配*a^n b a^n b a^n*堆栈自动机甚至无法识别的语言.另一方面,我很确定*a^n b^n*不能用这种方式表达.

我有两个问题:

1. 是否有关于这一系列语言的文献(UNIX-y常规).特别是,这些泵浦引理是否有一个版本？
2. 有人可以证明或反驳*a^n b^n*不能以这种方式表达吗？

Answer 1

a^nb^n 是 CFL。语法是

A -> aAb | e

你可以使用 RL 的泵引理来证明 A 不是 RL