# Mod-01 Lec-05 DFAs solve set membership problems in linear time, pumping lemma.

Skip to content
# Mod-01 Lec-05 DFAs solve set membership problems in linear time, pumping lemma.

##
13 thoughts on “Mod-01 Lec-05 DFAs solve set membership problems in linear time, pumping lemma.”

### Leave a Reply

Organisation & Society

smooth

One of the best video lecture in TOC.

at 8:57 Since DFA always scan from left to right,how will the DFA gets to know that these are the three last bits,

Excellent teaching by the professor. Thank you for this wonderful lectures.

ashume…..

Amazing Sir ….!! one of the best NPTEL lecture ….!!

how does condition 1 and 2 imply that v consists only of zeroes.

why does v consists only of zeroes?

pl explain

sir how can you remove v in the last ,,,, at a time you are removing v from uvw combination that will surely change the acceptence. For any regular language acceptance of string in machine will make effect if string is changed…. in this video at the last V is removed why?????? if we change string then there should be acceptance of string effected. explain plz

Awesome teaching,

Best TOC lecture I have ever seen.

Thank you very much sir.

There can be a more easy approach for this. Make an nfa then reduce it to dfa

We cannot have a 0 length 'v'. This violates the 2nd condition of the Lemma. The proof is therefore invalid.

A correct way to prove this is, if you pump u v^2 w, then you must have more 0s than 1s and therefor the language is not regular, because it violates the condition of the language.

pumping lemma starts at 43:00

32:00