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?

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?
Was there any restriction on the type of language of L (e.g. a context free language)?
You said it's a modified pumping lemma. Have you covered the unmodified one yet?
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 09:39 AM.
So thinking about how a finite state machine recognizes a string, why would the number of states be important?
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).
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.
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?
« Tablets/Phones by Google?  Who decided the waiting 'hourglass' icon should cease to be animated? » 
Tags for this Thread 