regex - 正規表現が不可能な文脈自由文法

Question

同じ言語を受け入れることができる正規表現を与えることが不可能な CFG の例があるかどうかを調べようとしています。

Answer 1

数えたり覚えたりする必要がある言語は、正規表現として表現できません。

たとえば、括弧のバランスをチェックする言語:

S -> { S } S

S -> ε

Answer 2

通常のマシン/式には限られた (事前に定義された) 数の状態しかないため、入力の以前の部分を (無限に) 「記憶」することはできません。

そのため、状態機械では次の式を認識することは不可能です: a ⁿ b ⁿ (n∈ℕ)

n ≤ x (x∈ℕ) に対してそのようなマシンを作成できますが、ℕ からのすべての可能な値に対してそれを実行できるステートマシンはありません。