Hello justin

Hello

Are you asking about (01)*

Could you help with the previous comment.

Are you asking about {a}

Yes of course.

pumping length is usually the number of states in the minimized DFA.

Is this clear

For finite sets, since there are no loops

You can take pumping length to greater than the longest string.

That way no w satisfies the pumping length criteria.

So the pumping lemma is always correct.

Yeah I could get that but couldn't get why the M.P.L of language {a} is 2.

always trivially correct and holds.

So for {a} you have maximum length string 1.

For me I think that it's M.P.L is 1.

So you take pumping length 2.

Can't we pump the string a alone?

If pumping length is 1 them w=a can be pumped.

But we can't pump a.

Because then a* will be in L which is not the case.

If we pump a, w=a, x=e, y=a,z=e

xy^iz = a^i

But clearly aa, aaa, aaaa, etc do not belong to L

L consists only of a.

So this is the usual trick that they do for finite sets, take pumping lemma to be larger than the length of the longest string in the finite set.

Okay.That's right.Could you give an example for why the M.P.L for language {a} is 2?

Suppose L = {a, ab, abbbab}

Then pumping length will be 7

That's for sure.

Pumping lemma condition is if w is longer than pumping lenth then it can be pumped.

You set pumping length 2, then w cannot be a.

Do you mean to say that we can pump only aaa but not a or aa?

It simply means that finite set cannot be pumped at all.

Because pumping always lead to infinite sets.

Because there are no loops.

DFA of finite sets will always be acyclic.

Could you explain a little bit more about finite sets in the context of DFA's.

Think how do you write a DFA or NFA for a finite language.

For NFA it is easy.

You take strings of finite language one by one, and add a path from start state to final state.

Isn't it.

Yeah that's right.

So when you convert into DFA there won't be cycles.

There can't be cycles.

Because if there is a cycle in DFA, your language becomes infinite.

Oh could you help me with that.

Why? Because you can go through the cycle as many times to go to final state.

Can't we have loops in DFA's?

Sorry I am talking of minimum DFA.

minimum DFA for finite languages.

We can have loops in DFA's for infinite languages.

In fact we should have loops in DFA's for infinite languages.

Does pumping lemma only hold for finite languages?

Pumping lemma holds for all languages for which DFA is possible.

It trivially holds for finite languages by taking pumping length very large.

For {a} you can take pumping length 10 or 100 too.

Since there are no infinite length string it doen't matter.

Okay.I would like to know how the M.P.L for language {a} is 2.Does this mean that we could only pump aa,aaa,aaaa etc?

It doesn't matter as long as you take pumping length >= 2.

But aa , aaa, aaaa do not belong to L, so first condition of pumping lemma is not satisfied.

first condition w belongs to L.

Could you list any string that could be pumped by the language {a}.

Exacly there are no strings.

No strings that can be pumped.

Therefore statement " If w in L, and |w| >= n then blah blah blah" is always true.

In a statement "If P then Q" if P is always false, then "If P then Q" is said to be always trivially true.

Could you show an example to show that M.P.L for language {a} is 2.

First note that it can't be 1.

Okay.

Let us take next number 2

Okay!

Yeah proceed.

Now what is the truth value for " w in L and |w|>=2" ?

Can it be ever true?

Say yes or no!

Oh I couldn't get that.Do you mean to say that it will always be true?

It will always be false.

Could you help me with that.

It will always be false for every w

w = a, w in L and |w|>= 2 : False

w = aa, w in L and |w|>=2: False

w = ababbb, w in L and |w| >=2: False

Oh do you mean to say for this particular example?Yeah I could see.

So if P then Q is equivalent to (not P or Q) is equivalent to (not False or Q) is equivalent to (True or Q) is equivalent to True

Always true.

Always trivially true.

So pumping lemma does not hold for 1

But pumping lemma holds for 2

SO minimum pumping length is 2.

Easy.

Could you tell why it holds for 2 but not 1?

Can you state pumping lemma?

Yes of course.

In your own words, not copy and paste.

Pumping lemma states that if a string w belongs to L then we could split the string as x,y,z where y is the part that could be pumped.

You need to correct it a bit.

If a string w belongs to L and w is longer than pumping length then blah blah

Oh I didn't remember about that.

Now pay attention to the if confition.

substitute L = {a} and pumping length = 2 in the statement

if a string w belongs to {a} and w is longer than 2 then blah blah

What can you say about the above statement.

Yeah I could see that you meant to tell that since for the language {a} the only valid string is a itself the statement would be trivially true isn't it?

Yes exactly

That is why pumping lemma holds for pumping length 2.

Clear?

I think I'm weak in M.P.L.Could you give an example for M.P.L.

Minimum pumping length is smaller than or equal to number of states in the minimized DFA.

This we get from the proof of pumping lemma.

Proof of pumping lemma is a constructive proof where we construct n to be number of states in the DFA.

If DFA is minimum then n is also kind of minimum.

At least min pumping length won't be larger than that.

Could you tell the M.P.L for this dfa.

I already told you it is 4.

4 is a pumping length because of the proof of pumping lemma.

It is minimum because 3 can't be pumping length.

So can we only pump strings that are greater than the M.P.L of DFA?

No, we can definitely pump strings that are greater than the MPL. But we can sometimes pump strings that are smaller than the MPL>

For example we can pump aba which is smaller than MPL. Yet there is a loop, and hence we can pump it.

Could you tell how could we relate the M.P.L and proof of pumping lemma.

The relation is this. Pumping lemma given a pumping length such that it is number of states in DFA.

We can construct a minimum DFA.

THerefore min pumping length is at most the number of states in minimum DFA.

it is at most number of states in any DFA.

So just by looking at the DFA I could tell that MPL is less than 4.

Okay.Yes that's correct.

But it can't be 3 because aaa can not be pumped.

so MPL is 4.

It can't be less that 3 also because aaa can not be pumped.

Can aa be pumped?

Sorry, So just by looking at the DFA I could tell that MPL is less than or equal to 4.

Please correct my earlier statement.

aa can not be pumped too

Either y = a or aa.

If y = a then you have aa, aaa,aaaa,aaaaa, etc

If y=aa then you have aa, aaaa,aaaaaa, etc

aaaa does not belong to L

It occurs in both the sequences.

so aa cannot be pumped.

Okay,Do you mean to say that we're paying attention to pumping length and not M.P.L?

Or for that matter a also cannot be pumped.

We are trying to find MPL. Aren't we.

Okay that's right.I meant to say regarding the proof of pumping lemma.

proof of pumping lemma only gives one pumping length.

It doesn't give minimum.

Yes.Can baa be pumped?

Remember I said "we can definitely pump strings that are greater than the MPL. But we can sometimes pump strings that are smaller than the MPL"

Since sometimes we can pump, does not mean anything.

It is important when we can not pump.

Could you tell when we can't pump?

Let me see the DFA and tell what cannot be pumped.

Okay.

3 length acceptable strings are bba, baa, aba, abb?

Are there any more?

Please check!

Yeah all are correct.I don't think we could pump baa because pumping baa generates the string baaa which doesn't belong to L.

No we can easily pump bba, baa and aba, because there are loops.

baa can be pumped aa, baa, bbaa, bbbaa, bbbbaa, etc.

Only remaining one without loop is abb. This the string that cannot be pumped

Possible values of y are

Oh sorry I again made a mistake by arbitrarily pumping than pumping by seeing the loops available.

(a)bb (ab)b (abb) a(b)b a(bb) ab(b)

These are the values of y

(y=a)bb , i=0 , bb not in L

(y=ab)b, i= 0, b not in L

(y=abb) i=0, e not in L

Yeah I could see that we can't pump abb.

a(y=b)b i= 2 abbb not in L

ab(b) i=0 ab not in L

So is the M.P.L for the DFA 3?

4

MPL is 4

because 3 can't be PL.

length of abb is 3

that is why 3 can't be PL

We already showed that abb can not be pumped.

Oh that's very right.I think we should consider all of the possible options to prove that the P.L for the DFA is 3 isn't it?I think that's a tedious task.Maybe that's why every one take P.L to be greater than or equal to the number of states in DFA isn't it?

Sometimes proofs are easier if we know the structure of language. For a general language minimum pumping length is difficult.

We just need to show a string which cannot be pumped for length MPL-1

You need to only to check strings for which there are no loops.

Of course that's right.

By this consideration it would be easy.

You might be thinking it was tough, but consider I have to type my answer, see the DFA and at the same time guess what your confusion is! :-)

Okay I have to go for my lunch. I am late already.

Yeah I could get your patience and effort.For the language {abb} which has 5 states.Isn't the P.L for the DFA 3 or is it 6 still ahead?

q0 -> a->q1->b->q2->b->qf

sorry four states.

so PL is 4.

I think there's a trap state too isn't it?

We don't consider trap state in pumping lemma, so we also don't consider it here.

Don't we need a trap state to make it a DFA?

Usually we remove all states from which final state is not reachable.

Could we call that an DFA.I'm not sure about it.

The trap state is only needed when we wan't to have complete DFA.

Okay.

If we do not have a transition we immediately say that the string in rejected.

It is not important but you can say pumping length is |Q|-1 if there is a trap state, |Q| if there is not.

So while considering the proof of pumping lemma do we discard trap states while looking for the number of states in DFA?

This you get from the proof of pumping lemma.

Yes, because in the proof, you consider a path that reaches final state.

trap state can never be in this path.

So the trap state is never considered at all.

And to make complete DFA only one trap state is needed. So we can merge all the different trap states into one.

I think that if there is a trap state then it's P.L would be |Q|-1 and if there isn't any trap state P.L would be |Q|-2 isn't it?

If there is a trap state then it's P.L would be |Q|-1 and if there isn't any trap state P.L would be |Q|

Not |Q|-2

Since we don't consider a trap state one state would be reduced isn't it.So total it's P.L would be |Q|-1-1 isn't it?

Consider a^*

There is no trap state.

PL cannot be -1.

Okay.Sorry what if the string is not an kleene closure of a?

Is n't one example enough for disproving something.

Oh couldn't get that.

Say i.stack.imgur.com/LxihX.jpg

This is another example.

Okay continue.

Where you don't have trap state.

Because it is a complete DFA.

Yeah that's true.

All transitions are defined.

PL is not 2 but 4.

Yeah I could get that.

No not a good example.

Yes that's obvious from the diagram since you need 4 steps to reach the final state.

Consider same DFA but final state Q1 and Q3

Okay.

Corresponds to either a or b is odd.

No take only final state Q1

Isn't it a or b or do you mean to say that the length of string is odd?

bab will not be a loop.

bab will not be pumped.

so MPL is 4

It is not 2.

Pumping lemma says in this DFA any 4 length accepted string will have a loop.

Okay,whether bb is a loop?

Yes bb is loop if bb is accepted by Q0 state.

If Q1 is final state, then whether bb is loop in string bb is meaningless.

Yeah but as you told earlier aa can't be pumped.Sorry for that.

aa can be pumped in this DFA if final state is Q0.

I am talking of this dfa: i.stack.imgur.com/LxihX.jpg

A DFA without trap state.

I think we're considering the final states as Q1 and Q3 as you have told isn't it?

No only Q1

If we are finding non pumped string better to have a DFA with many non-accepting states.

So take only Q1.

Okay.

bab is not a loop

but is accepted

but cannot be pumped.

Yes that's right.

So MPL is 4

|Q| = 4

Okay.

Can I go for lunch now?

Yeah sorry for driving you a bit more hungry.

Fine, bye.