regex - 不可能使用正则表达式的上下文无关语法

Question

我试图找出是否有可能有一个 CFG 的例子，它不可能给出一个可以接受相同语言的正则表达式。

Answer 1

由于常规机器/表达式只有有限（预定义）数量的状态，它不能“记住”（无限）输入的早期部分。

因此，对于状态机来说，识别以下表达式是不可能的：a ⁿ b ⁿ (n∈ℕ)

你可以为 n ≤ x 制造这样的机器，其中 x∈ℕ，但没有状态机可以为 ℕ 中的每个可能值做到这一点。

Answer 2

任何需要计数/记忆的语言都不能表示为正则表达式。

例如，检查平衡括号的语言：

S -> { S } S

S -> ε