Notices
Results 1 to 18 of 18
Like Tree5Likes
  • 1 Post By MagiMaster
  • 1 Post By MagiMaster
  • 1 Post By MagiMaster
  • 1 Post By MagiMaster
  • 1 Post By MagiMaster

Thread: Pumping Lemma

  1. #1 Pumping Lemma 
    Forum Freshman
    Join Date
    Dec 2013
    Posts
    10
    Hello!Could you give me a hint how to do the following exercise:

    Let L be the language, which has an infinite number of words, then there are words , so that , and each word is in L.How could we prove this modified Pumping Lemma?


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Was there any restriction on the type of language of L (e.g. a context free language)?


    Reply With Quote  
     

  4. #3  
    Forum Freshman
    Join Date
    Dec 2013
    Posts
    10
    Quote Originally Posted by MagiMaster View Post
    Was there any restriction on the type of language of L (e.g. a context free language)?
    I am at the chapter with the regular languages!!!
    Reply With Quote  
     

  5. #4  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    You said it's a modified pumping lemma. Have you covered the unmodified one yet?
    Reply With Quote  
     

  6. #5  
    Forum Freshman
    Join Date
    Dec 2013
    Posts
    10
    Quote Originally Posted by MagiMaster View Post
    You said it's a modified pumping lemma. Have you covered the unmodified one yet?
    Yes... Is the proof of the modified one similar to the original?
    Reply With Quote  
     

  7. #6  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    That might be worth trying at least. You could start by working through what's different between the two lemmas and seeing how that would affect the proof.
    jenny 66 likes this.
    Reply With Quote  
     

  8. #7  
    Forum Freshman
    Join Date
    Dec 2013
    Posts
    10
    Quote Originally Posted by MagiMaster View Post
    That might be worth trying at least. You could start by working through what's different between the two lemmas and seeing how that would affect the proof.
    The original lemma is:"Let L be the language of the automaton M, which has an infinite number of words, then there are words so that each word ."So the difference is that at the modified lemma has to be satisfied. But how can I show this?.What is the relation between the length of a word and the number of states?
    Last edited by jenny 66; December 14th, 2013 at 10:39 AM.
    Reply With Quote  
     

  9. #8  
    Forum Freshman
    Join Date
    Dec 2013
    Posts
    10
    I edited my previous post.
    Reply With Quote  
     

  10. #9  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    What is ?
    jenny 66 likes this.
    Reply With Quote  
     

  11. #10  
    Forum Freshman
    Join Date
    Dec 2013
    Posts
    10
    Quote Originally Posted by MagiMaster View Post
    What is ?
    It is the set of states!!!
    Reply With Quote  
     

  12. #11  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    So thinking about how a finite state machine recognizes a string, why would the number of states be important?
    jenny 66 likes this.
    Reply With Quote  
     

  13. #12  
    Forum Freshman
    Join Date
    Dec 2013
    Posts
    10
    Quote Originally Posted by MagiMaster View Post
    So thinking about how a finite state machine recognizes a string, why would the number of states be important?
    Because,there must be a final state,so that the machine recognizes the word... Or am I out off topic??
    Reply With Quote  
     

  14. #13  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Not exactly off topic, but the existence of a final state doesn't have much to do with the number of states (other than making it nonzero).
    jenny 66 likes this.
    Reply With Quote  
     

  15. #14  
    Forum Freshman
    Join Date
    Dec 2013
    Posts
    10
    Quote Originally Posted by MagiMaster View Post
    Not exactly off topic, but the existence of a final state doesn't have much to do with the number of states (other than making it nonzero).
    Has it maybe to do with the length of the word?
    Reply With Quote  
     

  16. #15  
    Forum Freshman
    Join Date
    Dec 2013
    Posts
    10
    Or am I wrong??
    Reply With Quote  
     

  17. #16  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Well, the length of the word is important too. Try posting what you've got so far and it'll be easier to point out where you're going wrong.
    jenny 66 likes this.
    Reply With Quote  
     

  18. #17  
    Forum Freshman
    Join Date
    Dec 2013
    Posts
    10
    Quote Originally Posted by MagiMaster View Post
    Well, the length of the word is important too. Try posting what you've got so far and it'll be easier to point out where you're going wrong.
    I don't really know how to start...Could you give me a hint?
    Reply With Quote  
     

  19. #18  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Start with a small example and work it by hand. Maybe try something like the FSM for . How many states would you need? What would x, y and z be? What happens when you try and run xz, xyz, xyyz through the machine? Why is the number of words and the number of states important here?
    Reply With Quote  
     

Similar Threads

  1. Tall buildings, pumping water up?
    By HexHammer in forum Physics
    Replies: 13
    Last Post: May 2nd, 2011, 02:30 PM
  2. Pendulum eases pumping of water
    By lexpopuli in forum Pseudoscience
    Replies: 1
    Last Post: February 25th, 2011, 06:54 PM
  3. CFL pumping lemma
    By zxczxczxc in forum Computer Science
    Replies: 0
    Last Post: January 12th, 2011, 12:12 PM
  4. Pumping lemma and minimization of Finite Automata
    By yoyo_tidus in forum Computer Science
    Replies: 0
    Last Post: October 9th, 2009, 03:44 PM
Tags for this Thread

View Tag Cloud

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •