设计上下文无关文法

Question

L(G) = {x^n # y^m | 0 <= 2m <= n <= 4m}

我如何为 S 是起始状态的上述语言设计上下文无关文法？

我不确定如何在中间添加一个井号。我的方法：S => xxxxSy | B | C | epsilon , B =>xxxBy, C => xxCy

Answer 1

让我们想象两种更简单的语言：x^2m # y^m 和 x^4m # y^m。这些 CFG 是什么样子的？

T := xxTy | #

F := xxxxFy | #

这些语法中的每一个生成的语言都是我们语言的一个子集。事实上，我们可以通过将 T 和 F 组合成一个起始符号 S:

来获得非常接近的结果

S := xxxxSy | xxSy | #

这非常接近，但是，它不能让我们生成奇数长度的 x 前缀。我们可以通过允许在 S := xxSy 规则期间添加一个额外的 x 并记住我们已经通过切换到一个新的非终结符 R:

来解决这个问题

S := xxxxSy | xxSy | xxxRy | #
R := xxxxRy | xxRy | #

我们现在可以通过归纳来证明这个语法是有效的：

基本情况：字符串 #（对于 m = n = 0）在该语言中。根据需要，语言中下一个最短的字符串是 xx#y、xxx#y 和 xxxx#y。

归纳假设：对于所有 m 到并包括 k 的语言，所需要的字符串都在语言中。

归纳步骤：我们必须证明所有需要的字符串都是m = k + 1的语言。我们知道所有需要的字符串都是y = k的语言；所以我们有 x^2k # y, …, x^4k # y。在末尾添加一个额外的 y 意味着我们在前面至少需要两个额外的 x（所以我们现在的最小值是 x^2k+2 # y^(k+1)）并且最多我们可以添加四个额外的 x（所以我们的最大值现在是 x^4k+4 # y^(k+1))。我们引入的 x 的唯一 "new" 个数是 x^4k+1、x^4k+2、x^4k+3 和 x^4k+4，我们可以得到它们如下：

将 S := xxxxSy 的一个应用更改为 x^4k # y^k 推导 S := xxxRy 和 R := xxRy 的一个应用得到 x^4k+1 # y^(k+1).
在 x^4k # y^k 的推导中添加 S := xxSy 的一个应用得到 x^4k+2 # y^(k+1).
在 x^4k # y^k 的推导中添加 S := xxxRy 的一个应用得到 x^4k+3 # y^(k+1).
在 x^4k # y^k 的推导中添加 S := xxxxSy 的一个应用得到 x^4k+4 # y^(k+1).

设计上下文无关文法

Design a context free grammar

context-free-grammar