CODEWITHSUNDEEP
regular-languagepumping-lemma
Olivia Pearls
Olivia Pearls

Reputation: 139

Minimum pumping length of L= {0^i1^j | i >= j} to prove L is non regular

Both Mr. Mithlesh Upadhyay and You play a game:
1. Mr. Mithlesh Upadhyay gives you a constant n.
2. You choose a word w in the language of length at least n.
3. Mr. Mithlesh Upadhyay gives you x, y, and z with xyz = w, |xy|≤n, and y not empty.
4. Now you pick r.
5. Mr. Mithlesh Upadhyay asserts that xyrz is also in the language.
6. If Mr. Mithlesh Upadhyay is wrong, you win.

    In case, if you win the game, what is the minimum possible value of 
your r for the language {0^i1^j | i >= j} ?

A. 0

B. 2

C. 3

D. Mr. Mithlesh Upadhyay won the game for given language.

Explanation Given, above game is known as Pumping Lemma for regular languages.

You won the game for the minimum value of r is 0.

Option (A) is correct.

I could not understand the solution. How is it possible to get 0 length min pumping length.If we take w = 01 and pump 1 , then it does not belong to L. So, why is 2 not the minimum length ?

Upvotes: 1

Views: 611

Answers (1)

Prateekshya Priyadarshini
Prateekshya Priyadarshini

Reputation: 11

According to point number 5 and 6, if you are the winner, it means that Mr. Mithlesh Upadhyay was wrong and xyrz does not belong to L. In your example you have shown that 011 does not belong to L. If you are going to make the minimum possible length of r to be 2, then your example will be wrong. Because you have taken r to be of length 1. Correct me if I'm wrong.

Upvotes: 1

Related Questions