Pumping Lemma for CFL

Two Pumping Lemmas

• 考慮一個無限的語言

  

  • 設定變數P、m

    

  • 挑選一個字串長度超過p

    

  • 在這個字串中必定存在重複的production

    

• 推論

  

  • 下一個產生字串的長度 會小於當前字串加上最長right hand side的production

    

    • 可以推得字串長度的上下界
    • 得知

      

    • 得到結論
    • k 會大於 p/f (Number of productions in grammar)
  • 因此存在重複的production

    
    

    • 某些variable會重複

• 派生

  

  • 得到可能的派生

    

  • 所以存在這樣的可能性

    
    

    • 這是原版
    • 差在其中A的production 有一個被去掉了

      
      
      

  • 所以有這樣的推理

    

    • grammar G 可以生成這樣的string

      

• 那因為A是 last repeat variable

  

• 因為沒有unit, null production

  

• 證明 pumping lemma

  

  • lemma 1 proof

    

  • Pumping lemma I

    

• Applications of The Pumping Lemma

  • Example

    
    

  • proof

    

    • 挑選string

      

    • 選出vxy

      
      

      • case I

        
        
        
        
        

      • case II

        
        

      • case III

        
        

      • case IV

        

        • possibility I

          
          
          
          

        • possibility II

          
          
          
          

      • …
    • In all case

      

• Non Context-free

  

• 第二種用法

  • 使用uv yz