Pumping Lemma (For Regular Languages)
ฝัง
- เผยแพร่เมื่อ 19 มี.ค. 2017
- TOC: Pumping Lemma (For Regular Languages)
This lecture discusses the concept of Pumping Lemma which is used to prove that a Language is not Regular.
Contribute: www.nesoacademy.org/donate
Website ► www.nesoacademy.org/
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Pinterest ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
• Axol x Alex Skrindo - ...
![USAB Showcase: Australia vs USA [OFFICIAL STREAM]](http://i.ytimg.com/vi/keiEr_MOaSQ/mqdefault.jpg)
We who are about to fail our computer theory tests salute you.
Cullen Johnson all hail Okasaki
my brethren!!!
tomorrow, I face my death
Professor before he even gives me the exam paper: *Omae wa mou shindeiru...*
i have watched all the videos of this tutorial and i have scored good marks....
Important to note that the pumping lemma should be used to prove a language is not regular only when that language is NON-FINITE. All finite languages are regular since they can be described by finite automata. This was confusing to me at first because you can trivially see that a finite language will not satisfy the pumping lemma.
Thanks I literally came here to check if a language that let's say only accepts w=a as an input will work with pumping lemma. Since a finite language with no variables can be described with an FSA without any loops it won't have parts that repeat themself. It's still a regular language by definition because there is a FSA that can describe it. Thanks again!
I think that last part is wrong. A finite language L trivially *satisfies* the pumping lemma: just set P to be larger than all strings in L.
And what about a language that only accepts words: a,ab,abc,abcd? There is no recurring part so x(y^i)z restriction couldn't be met, so pumping lemma wouldn't be satisfied. Correct me if I'm wrong. It is a regular language however because an FSA accepting that language does exist.
PatVax The pumping lemma can be used by setting the pumping length to 5. Thus the pumping lemma *vacuously* holds true for all such strings (length >=5) in your language since there are no such strings.
@@patvax532 Late, but the reason it is true is this: The pumping lemma states that for any regular language R, there exists n such that for all w ∈ R, *If* |w| > n *then* the conditions of pumping lemma hold.
From the truth table of implication, in a statement like *If* A *then* B, if A is false, the statement is true no matter what B is.
Hence if we can find any n larger than the length of all words in R (and we are guaranteed to be able to, if the language is finite), the statement is always true no matter what the form of the language is.
Thanks a lot for your lectures. I've watched a lot of lectures from you now & thought I should make a comment appreciating your contribution and hardwork into this.
You are explaining better than my professor. I have already watched all the videos from this section. Thank you very much for what you are doing.
my professor watches the same lecture 5 min prior to the class
I just love the way u teach sir... It helped me a lot...thank you
Awesome lecture and great music at the end.
thank you so much Neso Academy for this , covered whole chapter in 1 night before exam .
thank you for repeating some parts. it really helps me capture what you're saying.
Great lectures,your explanation is in a huge way,we are understanding very clearly and also provide gate lectures sir for theory of computation
Since there is NESO academy videos to teach me this stuff, I don't attend classes anymore, and I go to test and get maximum grade.
I feel like the video teacher is a robot because he always describe what he does or repeat very simple steps like an algorithm, but I guess that's what makes it a great teacher, easy to follow.
Thank you.
same
This is absolutely brilliant and you explain it in such an easy way!!!!
Thank you sir for these amazing videos!
Great to see that you are back!
really i love u Sir because u are the best lecturer i have ever seen thanks thanks. please complete for us the subject
Jaise hi mein ne apka lecture suna shuru kiya mein zor se phar rahi thi aur mere saare concepts clear ho gaye. Good job sir.
These videos will pump you up!
Thank you for your explanation 😊
Great sir! It helped me a lot
5. Method to prove that a language L is not regular
At first, we have to assume that L is regular. So, the pumping lemma should hold for L. Use the pumping lemma to obtain a contradiction
o Select w such that |w| ≥ n
o Select y such that |y| ≥ 1
o Select x such that |xy| ≤ n
o Assign the remaining string to z. o Select k such that the resulting string is not in L.
Hence L is not regular.
Thanks for the clear explanation.
Thank you so much sir for these amzing videos.
Sir, can you please upload videos of leftover topics of this subject soon. It'll be really helpful for us.
Thank you so much.
Man, what an explanation👍🏻👌🏼👌🏼👌🏼👌🏼 this is the 15th video I'm watching in a row and never liked this many videos in less time😁😁👌🏼👌🏼👍🏻👍🏻👍🏻
neso academy video lectues are fab!😍😍😍😍😍thankyou!
OK 👌
Rodrigo Félix is very thankful for your tutorial!
+rep
I think you are best teacher of TOC for me.
By far the best video
That was helpful. Thanks
I got a viva in 2 days and you are literally saving my life rn
that's quite helpful! thx!
In the statement of the lemma, it should be that S is a member of A. "If A is reg, there exists integer P such that all S in A with length at least P can be divided into xyz with these properties..."
String S is any word of language A
best lecture in youtube sir
Thanks ! You are Great !!!
Thank you sir😊
You teach 10x better than my prof.
better than my professor several times...
I really loved my professor for the class I took in which this is one of the topics, but he seriously stumbled over this explanation even though he explained everything else really well
Thanks a lot!
Very Useful
thanks very nuch this chanel good for this course
Thanks a lot
Thank you..Sir..
This guy is awesome!!
Thanku ♥️
pls add the video with example..
appriciable sir... can u please upload an example of this also...
Great Work . Some links in ur website are not working. Please Fix them.
Very helpful video :)
what is the pumping lenght? is it given ?
Gracias.
Thankyou sir
sir can you please tell the book u take reference from?
Should y be split into uvw and pump v
Allahu ekber, Elhamdulillah. Clear. Thank you Neso.
for the sake of us , you are doing a great job sir, hat's of you sir, i would like to know your name sir...
A man has no name XD
+Hrishikesh parab hahaha
ambn for m,n>=1 is regular or not . Has anybody tried Pumping Lemma for this? Plz explain
ur great sir
I hate my life
Y bro
Due bro
Why bro😊
Same bro
Womp womp
thanku sir
wait so what is it called when a language is neither regular nor non-regular?
aa(ab)*bb is Regular Language??? Can we prove it as non regular using Pumping Lemma?
If the length of v is equal to 0 isnt it against the second point of the th?
am i right in saying that case2 and case3 do not follow property 3 of pumping lemma? |xy|
in the next video
Plz upload data compression lecture sir
Tomorrow is my final exam can’t wait to get ride of this course😣
Hail Neso!!!
is P (pumoing length) denotes prime?
No it is not prime
It is named as pumping length
For example:
L = {a^n b^n} where n>0
Here pumping length is n
This is wrong. You don't get to choose pumping length p. You also don't get to choose how to "split" the string. You only get to choose the string s and i.
So how do you know what P is for a given language? I mean, I know I'm misunderstanding something here but it feels like this theorem as it is could be used to prove a regular language irregular by using the wrong pumping length.
You never know the exact value of P. The only thing you know is that such number EXISTS.
Essentially P is the smallest number of states a machine for that language can have + 1. So you usually do not know it, unless you know the minimal automaton.
You usually have to say, given P, .... so u dont get to chose the P, as you have to argue against EVERY possible P.
Awesome explanation. But can you please what is pumping length?
its the length of how much you expanded your regex. say you have a* this can be aaa or aaaaa or aaaaaa. the pumping length is how many times you expanded a. Thats the best explanation I can give from the tutorial.
@@Omar-kw5ui It's not the pumping length..Pumping length is defined as the minimum number of states required b the automaton to accept the finite language.
@@Omar-kw5ui right
i can not afford to buy paid your course. i am in 3rd sem now btech. pleaseeeeee dont remove these lectures. its is extremely helpfull.
Those here for exam tomorrow ! 🔥
👋🏻🙂
We find a string S and make all their possible divisions.
Video very good
a^n b^ n where n+m is even , how is this a regular language? one can prove it is not regular by pumping lemma, but I read online it is regular. Please help me understand this!
we can form regular expressions for this string i.e. it is recognizable by FSM, Hence it is regular.
Good
what is exactly p...how do you know that value.....
Best explanation ever 👌👌
Why do you have to show that all three conditions cannot be satisfied to have a contradiction? Isn't proving that any one of the three condition cannot be satisfied enough?
Yes any one condition is enough to prove a language non regular.
Thanks for teaching.
Can we say if we could not use pumping lemma to prove "Not regular", then it is regular?
Suppose regular language is a set, then the complement set is non-regular language.
If a language is non-regular we could use pumping lemma to prove.
If a language is regular we could not use pumping lemma to prove(2:44).
Thus If we could not use pumping lemma, then it would be regular.
It's same like somewhere wrong, but I could not find it.
plz help~
No, the pumping lemma cannot be used to prove a language is regular.
I believe there are non-regular languages that satisfy the pumping lemma, therefore this is just one method we can use to prove certain languages are non-regular.
An example would have been nice, but good explanation
Keine sorge, wir packen Hollas schon.
Explanation and representation is great!
#thumbsUp
Sir L={ww|w €(a+b)* is a regular or Non regular language according to pumping lemma plz make a video on this language. Thanks in anticipation
L is not a regular language. Let's choose for instance s=(b^p)a(b^p)a=xyz. If i=0 (or anything but 1), then s=xy^0z=(b^p-1)a(b^p)a which proves that L is not regular according to pumping lemma because p-1 != p
Tried to explain it the best I could but I study CS in my native language which is not English. Hope you got the gist though
I have a Theory of computation exam in a few hours 😅
Shout out to our professor who doesn't even teach us this lesson and let us watch NESO Academy's video instead, I'm so tired of you, I'm so annoyed!!! anyway thanks to NESO
LMAO🤣 Yoohh I'm here for the same reasons!!
tomorrow is my paper and you are my saviour ty sir
00:04 Pumping lemma is used to prove that a language is not regular.
01:07 The pumping lemma can be used to prove that a language is not regular.
02:09 The language can be divided into three parts: X, Y, and Z
03:16 To determine if a language is regular, three conditions from the pumping lemma must be satisfied.
04:16 To prove that a language is not regular
05:12 We need to find a string in language A such that its length is greater than or equal to the pumping length and then divide it into three parts X, Y, and Z.
06:18 The string s cannot be formed as a regular language.
07:15 Using the pumping lemma, we prove that a language is not regular.
Crafted by Merlin AI.
Sir pls make a video on pigeon hole principle
Intuition for why this lemma is true?
Cool
was your teacher Saurabh Shanu?
hii everyone;
i request u if like all video of sir then please click on add(advertisement) to support neso acdemy....
thanks
Advertisements wont take them anywhere at all. Instead if you want to support their purpose, Try to donate at
www.nesoacademy.org/donate
Just watched one minute of this before realizing it's not about English grammar.
I am really sad for on this incredible day, I did not understand what was going on in this video. Therefore consider this a formal complaint!
😢
?
60
👍👍💯
An indian to the rescue again 🤠
From nepal. Bsccsit😂