1. 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?

2.

3. Was there any restriction on the type of language of L (e.g. a context free language)?

4. Originally Posted by MagiMaster
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!!!

5. You said it's a modified pumping lemma. Have you covered the unmodified one yet?

6. Originally Posted by MagiMaster
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?

7. 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.

8. Originally Posted by MagiMaster
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?

9. I edited my previous post.

10. What is ?

11. Originally Posted by MagiMaster
What is ?
It is the set of states!!!

12. So thinking about how a finite state machine recognizes a string, why would the number of states be important?

13. Originally Posted by MagiMaster
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??

14. 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).

15. Originally Posted by MagiMaster
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?

16. Or am I wrong??

17. 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.

18. Originally Posted by MagiMaster
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?

19. 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?