context-free-grammar - 如何给出这个上下文语法

Question

如何为 L={w∈{a,b,c}*|w has more as than bs} 创建上下文无关文法

Answer 1

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

CFG：基本上，你需要限制你的语法，这样每当一个“b”被创建时，至少有一个“a”也在混合中。

提示：

1. 暂时忽略“c”
2. 写下有效语言可以开始和结束的方式（基本上是两个字符组合）并尝试从那里进行概括。