regular-language - 泛化 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*不能这样表达。

我有两个问题:

是否有关于该语言家族的任何文献(UNIX-y 常规)。特别是，是否有针对这些的泵引理版本？

有人可以证明或反驳 *a^n b^n*不能这样表达？

Answer 1

你可能正在寻找

Benjamin Carle 和 Paliath Narendran“关于扩展正则表达式”LNCS 5457

DOI:10.1007/978-3-642-00982-2_24

PDF 扩展摘要 http://hal.archives-ouvertes.fr/docs/00/17/60/43/PDF/notes_on_extended_regexp.pdf

C. Campeanu、K. Salomaa、S. Yu:实用正则表达式的正式研究，国际计算机科学基础杂志，卷。 14 (2003) 1007 - 1018。

DOI:10.1142/S012905410300214X

当然，可以前后跟踪他们的引文，以找到有关该主题的更多文献。