Let us call a string w periodic if w = u^n for some string u and integer n great

Question

Let us call a string w periodic if w = u^n for some string u and integer n greaterthanorequalto 2. (The number n and the period u can differ in two periodic strings w_1 notequalto w_2. E.g. 010101 and 001001 are periodic, but 0110101 is not.) Use the Pumping Lemma to show that the set of all periodic strings over the alphabet {0, 1} is not a regular language. Is the statement still true if the length of the period u is required to be smaller than a particular integer, say 5? Justify your answer.

Explanation / Answer

By the Pumping Lemma for Regular Languages, there exists a pumping length, p for L such that for any string s L where |s| p, s = xyz subject to the following conditions:

(a) |y| > 0
(b) |xy| p, and

(c) i>0,xyizL.

Let us assume u=(001)n , for all n>=2

So we have p=3.

Choose n=2; we get string w=00100. Clearly we have |w|>p

Assign x=0,y=0,z=1001

1) |y|>0
|y| is 1, which is greater than 0.
So condition 1 satisfied
2) |xy| p,
   we have |xy|=2, which is equal to p, i.e
   |xy|=2=p
   Condition 2 satisfied
3) i>0,xyizL.
   Lets take i=2. We get w = 0 00 1001; this is not a periodic string.

Therefore it is not a Regular Language.

Yes the statement is still true if length of u is less than 5. Consider u=(1010)n , n=2, where we take x=1,y=0,z=101010.
For i=2, we get 100101010 which is not periodic string and hence proving that it is not a regular language.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.