regex - CFL 的上下文无关语法

Question

enter code here你好，这是我的问题

为 CFL 提供上下文无关语法 L = {a^nb^mc^n | m, n ∈ N0}

我的回答是 S-> ASC| B A-> aA| a B-> bB| b C-> cC| c

不管我的回答与否？我不确定。需要一些帮助。提前致谢

Answer 1

你的语法生成语言

L = {a^n b^m c^k | m, n, k ∈ N0}

因为应用规则 A->aA 和 C->cC 的次数是独立的。如果你想要 n=k，那么你必须在同一规则中生成 a 和 c。例如像这样：

S -> aSc | B .

在第二阶段，您在中间生成任意数量的 b：

B -> bB | <empty string> .