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.

  1. how does condition 1 and 2 imply that v consists only of zeroes.
    why does v consists only of zeroes?
    pl explain

  2. 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

  3. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *