Sipser CH2 PROBLEMS'ANSWER 2.33-2.42

2.33

考虑pumping length为 ,对字符应用pumping lemma.

1. 对情况1:只在里，

   • 对于,
   • 设,字符为
   • 已知，只需
   • 因为,,不可能整除比自己小的数
   • 矛盾，此情况不成立

2. 对情况2: only consists of b

   • ,
   • ,Consider and
   • ,
   • ,不可能整除
   • Contradiction.

3. For 3 : in the boundary of and

   • ,
   • 如果,则
   • 若,退化至情况1
   • 若,,
   • 令,,
   • ,
   • ,
   • Contradiction

结论：F is not CFL

2.34

• 对,验证不成立
• 对,
  • 验证时，,
  • 验证时，,
  • 成立

2.35

• 设派生树的高度为,至多有个叶子结点，生成的字符长度,对于的CNF文法生成的派生树有
• 设派生出长度为的字符需要步，,
• ,是整数，
• ,,
• 高度为的树至少有个变量，必定有变量重复一次
• 仿照泵引理证明，我们有三种规则
• 反复利用规则2造出无限集合

2.36

2.37

• 思路为选取合适的泵长度,使解析树的高度至少为,导致至少有一个变量的三次重复。满足条件a
• 详情见Gemini的回答
• 说实话条件b,c没看懂

2.38

• 考虑CFL，,,perfect shuffle为
• 应用pumping lemma易验证 is not CFL

2.39

• 考虑CFL，,，
• Regular Language，
• is 's shuffle,
• 应用pumping lemma易验证 is not CFL
• is not CFL

2.40

• is infinite,Prefix-closed CFL.
• Use Pumping Lemma: is an infinite subset of ,
  • ,a prefix of is , is infinite and regular
  • ,a prefix of is , is infinite and regular
• contains an infinite regular subset

2.41

• For :
  • • 该运算意为字符去掉任何后缀不能在L中，故舍去
    • 在时可能成为的前缀，舍去
  • 应用泵引理易验证 is not CFL
• For 同理，意为添加任何后缀不能在L中

2.42

考虑,应用泵引理易验证