如何给这种背景下语法

Question

如何创建上下文无关文法为L = {w∈{A，B，C} * | W有更多的作为比BS}

Answer 1

首先，你可以说服自己这是可能的通过下推自动机形式来思考它。非正式地：读取磁带时，将任意“a”推入堆栈，但在读取“b”时弹出堆栈。当磁带读取完成时，接受堆栈是否有“a”。否则拒绝。

CFG：基本上，您需要绑定语法，以便每当创建“b”时，组合中至少还有一个“a”。

提示：

1. 忽略“C”为位
2. 写下一个有效的语言就可以开始和结束（基本上是两个字符的组合），并尝试从那里推广的方式。