从语言到无上下文语法[关闭]

1 回答

• 1

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

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

  S -> eefff | eSf | eSff
  

  获得候选人后，您可以尝试使用数学归纳法证明它 . 在我们的情况下：

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

  归纳假设：假设语法生成语言中的所有字符串，并且语法生成的所有内容都使用语言，对于所有长度不超过k的字符串 .

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

  • 使用 S -> eSf 或 S -> eSff 生成由语法生成的长度为 k+1 的字符串 . 在第一种情况下，从 RHS 上的 S 派生的字符串的长度为 k-1 ;在第二个，它的长度为 k-2 . 在这两种情况下，字符串都是由感应假设的语言 . 也就是说，h <i <2h . 但是然后（h 1）<（i 1）<（i 2）<2（h 1），所以在任何一种情况下，字符串仍然是语言 .

  • 考虑语言中任何长度为 k+1 的字符串 . 我们有h i = k 1且h <i <2h . 任何这样的字符串必须以一定数量的e 's and end with some number of 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中，我们可以消除第1和第4个条件 . 剩下的东西永远不会满足 . 这表明至少有一个子串也在语言中 . 通过归纳假设，该字符串由语法生成 . 要从该字符串中获取长度为 k+1 的字符串，只需应用 S -> eSf 或 S -> eSff ，具体取决于语言中的哪个子字符串（两者都可以） .

  回复于 2024-04-30T13:44:57+08:00