grammar - 如何构造生成语言 L 的语法？

Question

我正在上正式的语言课，即将进行语法测验。我假设会出现这样的事情。

考虑字母表 ∑ = {a, b, c}。构造一个生成语言 L = {bab^nabc^na^p : n ≥ 0, p ≥ 1} 的文法。假设起始变量为 S。

Answer 1

自从我最后一次使用形式语言以来已经很长时间了，所以，请原谅我的生疏，但这将是语言：我们分为S前缀变量 ( A) 和后缀变量 ( B)。然后，我们分别处理前缀和后缀，它们都有一个可能的进一步递归规则，以及一个空的结束符号，不需要出现，而常量则至少需要出现一次。

{bab^nabc^na^p : n ≥ 0, p ≥ 1}

S -> ASB
A -> babAabc
A -> {empty}
B -> Ba
B -> a