grammar - 从语言到上下文无关语法

Question

给定语言 K = {e^hf^i | 2h > i > h} 我需要生成上下文无关文法

我想出的一些生产规则是：S -> eeTfff 和 T -> eTff | ε

它们仅在 n = m + 1 时起作用，但我不知道如何为 2h > i > h 中的每个组合生成任何规则。

Answer 1

首先，确定语言中最短的字符串。我们需要 i > h，所以我们可能会猜测 h = 0；然而，这无济于事，因为我们不能满足 2h > i。我们遇到了同样的事情 h - 1。选择 h = 2，i 的唯一选择是 3。所以语言中最短的字符串是 eefff。不能有任何其他长度为 5 的字符串。

要获得更长的字符串，我们可以在前面添加 e 或在末尾添加 f。显然，如果我们在前面添加一个 e，我们必须始终在末尾添加至少一个 f，并且永远不要超过两个 f。我们可以确认 e.eeff.f 和 e.eefff.ff 都在我们的语言中。这表明了一个语法：

S -> eefff | eSf | eSff

找到候选人后，您可以尝试使用数学归纳法来证明它。在我们的例子中：

基本情况：语言 eefff 中最短的字符串由产生式给出S -> eefff。

归纳假设：假设文法生成语言中的所有字符串，并且文法生成的所有内容都在语言中，所有长度不超过 k 的字符串。

归纳步骤：我们必须证明（1）由文法生成的长度为 k+1 的字符串在语言中，（2）在语言中长度为 k+1 的字符串是由文法生成的。

1. k+1由语法生成的长度字符串是使用S -> eSf或生成的S -> eSff。在第一种情况下，从Son派生的字符串RHS有长度k-1；第二，它有长度k-2。在这两种情况下，字符串都是归纳假设的语言。也就是说，h < i < 2h。但是 (h+1) < (i+1) < (i+2) < 2(h+1)，所以无论哪种情况，字符串仍然是语言。

2. 考虑语言中任何长度k+1的字符串。我们有 h + i = k + 1 和 h < i < 2h。任何这样的字符串必须以一定数量的 e 开头并以一定数量的 f 结尾。考虑长度k-1和的子串k-2。通过排除第一个 e 和最后一个和两个 f 形成。前者要么是语言中的字符串，要么后者是。要看到这一点，假设两者都不是。但是，(h-1) < (i-1) < 2(h-1) 和 (h-1) < (i-2) < 2(h-1) 都不是。那是：

   ((i <= h) or (i >= 2h - 1))
   

   和 ((i <= h+1) 或 (i >= 2h))

因为我们知道 h < i < 2h 因为我们的字符串在 L 中，所以我们可以消除第一个和第四个条件。剩下的永远不会满足。这表明至少有一个子字符串也在该语言中。根据归纳假设，该字符串是由语法生成的。要从该字符串中获取长度k+1字符串，只需应用S -> eSf或S -> eSff，这取决于语言中的子字符串（两者都可能）。