« first day    last day (20 days later) » 

justin
justin
6:18 AM
Good morning.Why does pumping lemma specifically says that "every xy^iz will be in L" .Why couldn't it tell that "every x^iyz will be in L".
 
Shreesh
Shreesh
6:30 AM
Hello
 
 
2 hours later…
justin
justin
8:17 AM
Could you help me with the previous comment.
 
Shreesh
Shreesh
8:32 AM
I have only 10 minutes. Are you there?
 
justin
justin
Yes of course.
 
Shreesh
Shreesh
If you read the prove of pumping lemma it only says that xy^iz will be in L. x^iyz may or may not be in L. Either thing is possible.
And also it says there exists a partition xyz such that xy^z will always be in L.
 
justin
justin
Could you show an example to prove that x^iyz would not be in L.
Could you name a string that will not be accepted by this split.
 
Shreesh
Shreesh
Sorry we need to take 4 length string for pumping lemma.
 
justin
justin
Okay
 
Shreesh
Shreesh
8:43 AM
w = abaa
there is a loop at ba so y =ba
x = a
y=ba
z = a
Now a(ba)^ia will be always in L
But not so a^i(ba)a
strings are baa abaa aabaa aaabaa aaaabaa
 
justin
justin
Could you name a string that will not be accepted by this split.
 
Shreesh
Shreesh
aabaa does not belong to L
See you reach back to q0 by this string
which in non-acceptable state
DO you understand that aabaa is not accepted?
Say yes or no
 
justin
justin
Oh sorry I think that it goes to q1 which is a final state.
 
Shreesh
Shreesh
Can you check again?
Yes you are correct
abaa is wrong choice
Let me give another string
 
justin
justin
Yeah proceed.
 
Shreesh
Shreesh
8:51 AM
aaaa
x = a
y=aaa
z = e
y is a loop
So xy^iz will always be in L
But not x^iyz
Strings are
aaaa, aaaaa, aaaaaa, aaaaaaa, aaaaaaaa
 
justin
justin
I'm looking for a string that will not be accepted by this split.
 
Shreesh
Shreesh
aaaaaa
Idea is to finish either at q0 or q3
Another example w = ababb
 
justin
justin
Yeah that's right.Okay take this split
x=aa
y=a
z=a
 
Shreesh
Shreesh
z = a you mean
 
justin
justin
yes of course
take the string aaaaaa for xy^iz
 
Shreesh
Shreesh
9:00 AM
But y is not a loop
y should be a loop
There is only one loop in aaaa, y=aaa
You cannot split arbitrarily in pumping lemma, y has to be a loop of some sort.
 
justin
justin
Can't we make y=a a loop by repeating a(or y).
 
Shreesh
Shreesh
No you have to get loops from DFA that you have drawn.
You have to take help of DFA to find out loops
 
justin
justin
Okay but whether y=aaa a loop as you have mentioned.
 
Shreesh
Shreesh
Yes it is
x = a q0->q2
y = aaa q2->q1->q0->q2
So it is a loop
 
justin
justin
Isn't there four a's there?
 
Shreesh
Shreesh
9:07 AM
One a for x, three a for y
 
justin
justin
Oh sorry that's right.
 
Shreesh
Shreesh
Since y is a loop
You can go through loop as many times you want but still end at q2
That is the simple meaning of pumping lemma
so a(aaa) a(aaa)(aaa) a(aaa)(aaa)(aaa) a(aaa)(aaa)(aaa)(aaa) are all accepted according to pumping lemma.
 
justin
justin
Yeah that's perfect.
 
Shreesh
Shreesh
If you think about pumping lemma in this way then it is very easy to understand.
xy^iz
x to reach to the loop
y go through loop as many times
z reach accepting state from the loop
 
justin
justin
Yeah I always forgot about reaching the loop.I always tried in reaching the final state.
 
Shreesh
Shreesh
9:12 AM
Okay if confusion is cleared, I am happy, I have to go now.
 
justin
justin
Yeah for sure.Thanks for your cooperation.
 
Shreesh
Shreesh
Bye
 
justin
justin
Take care.
Oh sorry.
Could you tell about this string aaaab
 

« first day    last day (20 days later) »