400 views
2 votes
2 votes
0^3m over the alphabets {0,1} , m E I+ is a regular language right? We can draw the DFA for it.

Which means it cannot be tested using pumping lemma for regularity, but since we already know it is regular, whenever we take any string generated by L and pump it, it should always be a member of the strings in L(M), right?

So, if I take 0^3p , p as the Pumping lemma const.,
Then |xyz| >p .
|xy|<p => |y| < p => pumping y we have 0^(3p+k) .

We can take |y|=1 without violating the pumping lemma constrains , so that on pumping, we have 0^(3p+1) , not acceptable by the machine.

Where have I messed up?

1 Answer

2 votes
2 votes
you are fixing |y| to be one. Pumping lemma doesn't say for every length of y it'll work. Pumping lemma only says that there is a y which will work.

So we can't assume y to be of size exactly 1. You can only say it's greater than or equal to one.

Related questions

0 votes
0 votes
0 answers
1
rahul sharma 5 asked Jan 11, 2017
501 views
In pumping lemma it says if there is a string whose length is >=N,where N is number of states in dfa,then language of machine is infinite,but there is one upper constrain...
4 votes
4 votes
2 answers
3
monty asked Oct 28, 2016
2,457 views