上下文无关的语法，不可能使用RegEx [英] Context Free Grammar for which a RegEx is impossible

问题描述

我正在尝试找出是否有可能提供无法接受可以接受相同语言的正则表达式的CFG示例。

I'm trying to find out if its possible to have an example of a CFG for which it is impossible to give a Regular Expression which can accept the same language.

推荐答案

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

Since a regular machine/expression has only a limited (pre-defined) number of states, it cannot "remember" (infinitely) earlier parts of the input.

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

As such recognizing the following expression is impossible for a state-machine: aⁿbⁿ (n∈ℕ)

对于n≤x，您可以制造这样的机器，其中x∈ℕ，但是对于from中的每个可能值，没有状态机可以做到。

You could make such a machine for n ≤ x, where x∈ℕ, but no state-machine can do it for every possible value from ℕ.

这篇关于上下文无关的语法，不可能使用RegEx的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！