http://www.geocities.ws/creatorgang/pl.htm

Pumping Lemma for Regular Grammars



A. Karthikeyan




 
   
 
 
   
 

Pumping
    Lemma for Regular grammars is said to be the toughest idea to understand. Here I tried it
    in my own way to make you to understand the concept.

 


   

Pumping Lemma is a powerful tool to prove a language is
    not regular. The proof technique used here is Proof by Contradiction.
    ie., initially, in the proof, the language is considered as a regular language. The
    following table shows how and where pumping lemma used exactly:


   

     
       
       
       
     
     
       
       
       
     
     
       
       
       
     
   
 

Regular Languages

Non-Regular
        Languages

can be applied to YesNo
to proveNoYes

   

The finite automata is simply a (virtual) machine and
    has no additional memory. It doesnot keep track of how many input symbols read. It just
    checks for whether the input string empties when reaching its final states.



   Below is the illustration done to
understand the concept of Pumping Lemma:




[圖]
 



In the above figure, the Conceptual Finite Automata
is depicted by an ignorant person at the left side.He doesnot know whether the string("water")
is in Language("bucket") or not. He simply pumps and
pumps the string. Pumping lemma("Thatha") knows that
some strings are not in language.(as he says,"water overflows")



One more illustration that considering pumping lemma as a GAME(taken
from the well-known author - PETER LINZ)
:









 


 

--
※ 作者: ott 時間: 2014-01-03 03:19:57
※ 編輯: ott 時間: 2014-01-03 03:32:35
※ 看板: ott 文章推薦值: 0 目前人氣: 0 累積人氣: 145 
分享網址: 複製 已複製
guest
x)推文 r)回覆 e)編輯 d)刪除 M)收藏 ^x)轉錄 同主題: =)首篇 [)上篇 ])下篇