Formal Definition of Non-Deterministic Finite Automata (NFA)

แชร์
ฝัง
  • เผยแพร่เมื่อ 23 ธ.ค. 2024

ความคิดเห็น • 198

  • @mohammadfaraz2352
    @mohammadfaraz2352 6 ปีที่แล้ว +335

    I have seen all lectures....It's wonderful. Got highest in the last semester.

    • @astroash
      @astroash 4 ปีที่แล้ว +16

      Damn bro

    • @muhammadfaraz8569
      @muhammadfaraz8569 4 ปีที่แล้ว +2

      Same Really helpful brother ....💞💝

    • @subid.majumdar
      @subid.majumdar 3 ปีที่แล้ว +5

      If you made any notes can you please send me the drive link, it'll help a lot 🙏

    • @collegematerial5348
      @collegematerial5348 2 ปีที่แล้ว +1

      From which book Or from which online source you pratice

    • @harshitchaurasia9027
      @harshitchaurasia9027 12 วันที่ผ่านมา

      my friend had studied from your videos, he passed

  • @girishtripathy3354
    @girishtripathy3354 5 ปีที่แล้ว +222

    Wasted my 2 hrs in class. Should have watched this instead. This series is very nice. Love you sir.

    • @nahomaraya2377
      @nahomaraya2377 3 ปีที่แล้ว

      fr man

    • @Shelly-kx2wz
      @Shelly-kx2wz 3 ปีที่แล้ว +3

      Never attended my lectures after watching this. I aced my exams for this subject.

    • @ashleynjeri.n.
      @ashleynjeri.n. 3 ปีที่แล้ว +3

      Wasted a whole semester!

    • @ashokkumaran5752
      @ashokkumaran5752 3 ปีที่แล้ว +1

      class made this subject a boring one

    • @morriswaithaka5132
      @morriswaithaka5132 2 ปีที่แล้ว +1

      @@ashleynjeri.n. 😂😂😂Njeri enda class

  • @therealjuggernaut1303
    @therealjuggernaut1303 5 ปีที่แล้ว +54

    You're such a legend. Exam tomorrow... learned more in 2 hours of vidoes than 2 months of uni. Tytyty

  • @ArthurGarreau
    @ArthurGarreau 2 ปีที่แล้ว +52

    For anyone wondering if 2^Q is wrong, it is not. The notation 2^Q is a special notation of the "power set" of Q.
    The power set of Q is a set of all the subsets of Q.
    In the example : the power set of Q is { empty set, {A}, {B}, {A, B}}

    • @benhayter-dalgliesh5794
      @benhayter-dalgliesh5794 ปีที่แล้ว +5

      Cheers, this confused me for a long time.

    • @mufurr
      @mufurr 9 หลายเดือนก่อน +1

      Oh thanks, I didn't know this was a notation. I was about to leave a comment about that lmao

  • @animegirl2146
    @animegirl2146 ปีที่แล้ว +5

    Love love love your explanations, never felt this confident about TOC before!!!

  • @lan2562
    @lan2562 2 ปีที่แล้ว +6

    Вы так доходчиво объсняете! 3 года ваши лекции выручили на первом курсе, и сейчас, на четвертом, вы меня снова спасаете! от всей души благодарю!!!

    • @igagankapoor
      @igagankapoor 11 หลายเดือนก่อน +1

      You'll be so clear about it! For 3 years, your lectures helped me out in the first year, and now, in the fourth year, you are saving me again! Thank you from the bottom of my heart.
      This is the translation.

  • @privatejr2702
    @privatejr2702 3 ปีที่แล้ว +10

    man I love your channel. When i graduate and work one day I'm gonna come back here and make a big contribution.

  • @NavalKishoreBarthwal
    @NavalKishoreBarthwal 6 ปีที่แล้ว +6

    9:21 it maps to (cardinality of alphabets) raise to the power (number of states)

  • @kartiknair5690
    @kartiknair5690 3 ปีที่แล้ว

    Thanks!

  • @tasneemsakifibnealam949
    @tasneemsakifibnealam949 5 ปีที่แล้ว +6

    Thank you. Your lectures are very easy to understand and it helped me a lot. Keep up your good work.

  • @JishuSengupta-rg5dw
    @JishuSengupta-rg5dw ปีที่แล้ว +1

    timro videos easy to understand hoyo.. molai samjh ma ayo daju! Thank you so much❤️

  • @monas.7095
    @monas.7095 4 ปีที่แล้ว +2

    This series of lectures of Finite automata are very helpful

  • @purnamuddangula9746
    @purnamuddangula9746 7 ปีที่แล้ว +1

    sir clear expalnation and byed d bay the mucic while starting of the video is awesome

  • @krisp2598
    @krisp2598 ปีที่แล้ว +10

    raise your hand if anyone is speed running this at 2x speed one day before the exam

  • @CrustyQtip
    @CrustyQtip 6 ปีที่แล้ว +87

    these are so much better at 1.5 speed

  • @pavithravenkatesan7216
    @pavithravenkatesan7216 5 ปีที่แล้ว +4

    Thank you for the fantastic tutorial. It's very helpful.

  • @gauravshah2674
    @gauravshah2674 3 ปีที่แล้ว +10

    I don't trust college. I'm doing my engineering from here. Thank you. You are a great teacher.

    • @Mithun526
      @Mithun526 3 ปีที่แล้ว +3

      HaHahaaaaa

  • @tinashenyahumbi8585
    @tinashenyahumbi8585 2 ปีที่แล้ว +3

    in previous lecture you said the DFA is easy to design too, so does it mean we cannot use that as a difference when asked?

  • @TROYENALINETTE
    @TROYENALINETTE 10 หลายเดือนก่อน +1

    I have a question: the L = set of all strings that end with 0, how does it know that the string is ending? and what if it decide to go to B but there is still another symbol 1, where will that symbol go?

  • @hectorg362
    @hectorg362 5 ปีที่แล้ว +4

    I freaken love you and this channel for this content!

  • @varunsingh9432
    @varunsingh9432 6 ปีที่แล้ว +5

    dear sir,
    why the state"A" when having an input 1 remain to the initial state but when it gets "0" it goes to the next state ? Pls explain​

  • @sirius_110
    @sirius_110 11 หลายเดือนก่อน +2

    I could not understand how A would reach AB on getting input 1 and what is really meant by AB in particular? Is there anyone who has some got answer for my query?

  • @trywellwashington7506
    @trywellwashington7506 4 ปีที่แล้ว +1

    6:47 how does A ( a certain input) ever gives phi (nowhere)? you mean it could ultimately give phi, after also going through B?

    • @eldqvist
      @eldqvist 4 ปีที่แล้ว

      the mappings are for the general case. Essentially I see it as, if you had 2 states and any given NFA what are the maximum possible states? The empty state is one of these

  • @explotuber6136
    @explotuber6136 5 ปีที่แล้ว +3

    at 5:14 B should be {B}

  • @kaanozyerstudent6624
    @kaanozyerstudent6624 2 ปีที่แล้ว

    you saved my life, thank you so much

  • @akshitdayal2689
    @akshitdayal2689 5 ปีที่แล้ว +1

    Thank you very much!! Really Helpful!
    -From India

    • @oskarjung6738
      @oskarjung6738 5 ปีที่แล้ว +1

      Lol, this channel belongs to an Indian only!!

  • @gamersbaxe4126
    @gamersbaxe4126 10 หลายเดือนก่อน

    What a topic thanks to Neso academy

  • @beAshishAdhikari
    @beAshishAdhikari 4 ปีที่แล้ว +1

    For the delta thing, shouldn't it be a power set of Q --> P(Q) instead of 2^Q. Because 2^Q denotes the number of elements in the power set. Please tell me if I am wrong.

    • @marxman1010
      @marxman1010 3 ปีที่แล้ว

      You are right. Do have some issues, but still a wonderful and best autamata course.

  • @azizbekibnhamid642
    @azizbekibnhamid642 4 หลายเดือนก่อน

    Tanks for amazing lessons

  • @coashe
    @coashe 10 หลายเดือนก่อน

    You are simply the best

  • @boblewis1287
    @boblewis1287 3 ปีที่แล้ว

    Please do a video on complete and non complete that baffled ne all these years

  • @parikshit804
    @parikshit804 6 ปีที่แล้ว +10

    how can giving 1 to A result in going to AB at 7:25 ?

    • @eldqvist
      @eldqvist 4 ปีที่แล้ว

      the mappings are for the general case. Essentially I see it as, if you had 2 states and any given NFA what are the maximum possible states?

    • @prashanthi8492
      @prashanthi8492 4 ปีที่แล้ว

      @@eldqvist how null is considered as state,could you elaborate it?

    • @eldqvist
      @eldqvist 4 ปีที่แล้ว

      @@prashanthi8492 it's an NFA = Non Deterministic, so null can be a state, same as multiple paths can be taken

    • @prashanthi8492
      @prashanthi8492 4 ปีที่แล้ว

      @@eldqvist yeah I understood after watching full , anyways thanks

  • @devmahad
    @devmahad ปีที่แล้ว +1

    In this video we are discussing the formal definition of non deterministic finite automaton. non deterministic finite automaton can be defined using five set of tuples. Q, which is the set of all states. Sigma, which is the set of Inputs, Q, not. which is the start state , initial state. F, which is the final state, set of final states. And lastly, we have Epsilon, which is the transition function. And has 2 raise to the power Q, possibilities. Because we have non determinism.

  • @nigussieeshete2926
    @nigussieeshete2926 5 ปีที่แล้ว

    i like your explanation about this course

  • @subid.majumdar
    @subid.majumdar 3 ปีที่แล้ว

    Why A after getting input 1 will go nowhere? Confused...... 7:10

  • @classmate3146
    @classmate3146 5 ปีที่แล้ว +1

    TNX a lot Sir, How A by 1 can goes to B?

  • @sanasohail3108
    @sanasohail3108 5 ปีที่แล้ว

    THANK YOU for uploading this topic...it helped me alot. thanks sir ...

  • @srikanthnalluri9610
    @srikanthnalluri9610 5 ปีที่แล้ว +3

    Sir please upload network security videos

  • @uditisinha357
    @uditisinha357 ปีที่แล้ว

    the formula 2^Q holds for all NFA? isnt it specific to the example taken? eg if A didn't have a self loop many possibilities wouldn't occur from the ones that were written for 3 states right?

  • @nomen385
    @nomen385 4 ปีที่แล้ว +8

    I was thinking instead that it maps it to the power set of Q
    d : Q × E ---> P(Q)
    What do you think

    • @vikramsamanta3780
      @vikramsamanta3780 3 ปีที่แล้ว

      Quite right. DFA maps to Q and nfa to 2^Q.
      By the way nfa is Q×(E U {€}) --> P(Q)

  • @emmanuelakpaklikwasi4300
    @emmanuelakpaklikwasi4300 9 หลายเดือนก่อน

    You are the best 😊

  • @gedelasivakrishna
    @gedelasivakrishna 2 หลายเดือนก่อน +1

    Thankyou !!

  • @LazyRider44
    @LazyRider44 7 ปีที่แล้ว +1

    Sir, if the alphabet set has more than two symbols what will be transition function? Will it be n^Q? n is no of input symbols.

    • @arcisd
      @arcisd 6 ปีที่แล้ว

      it happens when the function is not necessarily well defined, it is just a relation!

  • @imanezineddine7986
    @imanezineddine7986 3 หลายเดือนก่อน

    You are a legend.

  • @manavmalhotra8513
    @manavmalhotra8513 5 ปีที่แล้ว +1

    What happens when nfa final state could get a input?

  • @AhamedKabeer-wn1jb
    @AhamedKabeer-wn1jb 3 ปีที่แล้ว

    Thank you.. Well explained..

  • @KKukreja
    @KKukreja 4 ปีที่แล้ว

    For those wondering why is it 2^Q, it is because nC0 + nC1 + nC2 + ... + nCn = 2^n

  • @Oneminutecover-dx8re
    @Oneminutecover-dx8re 10 หลายเดือนก่อน

    I understand the combination formula, but don't get how fro state A went to state Fi when ita not drawn as possible...

  • @adityabikramsingh9855
    @adityabikramsingh9855 7 ปีที่แล้ว +1

    Sir ,
    At 7:23, if A get the input 1 then it can only go to A it self .......then how you mention A,B,AB,..

    • @MindLessbyPargatMann
      @MindLessbyPargatMann 7 ปีที่แล้ว +1

      sir said " 'A' on getting a certain input" not 1, although he writes 1 there

    • @matheusassis6601
      @matheusassis6601 7 ปีที่แล้ว

      I think it's a "i" for "input", not a "1". It's a generalization.

    • @abdulwasaykhan6438
      @abdulwasaykhan6438 6 ปีที่แล้ว

      @@matheusassis6601 Yes, I can see a small dot there. it's an i for any input

  • @coco9847
    @coco9847 3 หลายเดือนก่อน

    I don’t get how,there are possibilities to go any state if there is no transition between them ?

  • @indhumathi4783
    @indhumathi4783 ปีที่แล้ว

    Thank you sir❤️

  • @nileshthakur8989
    @nileshthakur8989 6 ปีที่แล้ว +2

    Thanku so much . My doubt is cleared that why the transition function maps to 2^Q.

    • @streetdogfamily3920
      @streetdogfamily3920 6 ปีที่แล้ว +3

      there was a slight error actually...it would be 2^ |Q| .....cardinality of Q ..as Q is a set ..we cant use it directly to formula..':)

    • @tomashaddad
      @tomashaddad 3 ปีที่แล้ว

      ​@@streetdogfamily3920 no, 2^Q is notation to denote powerset, 2^|Q| is a cardinality, i.e. |2^Q|, you can't have a cardinality as a codomain

  • @soumyadebbiswas5381
    @soumyadebbiswas5381 3 ปีที่แล้ว

    Sir please keep up the videos Sir!We are a strong team together!!

  • @sudiptacoachingcentre4118
    @sudiptacoachingcentre4118 2 ปีที่แล้ว

    It's really helpful

  • @Daniel_CLopes
    @Daniel_CLopes 5 ปีที่แล้ว +1

    Fenomenal!

  • @iliusahamad6724
    @iliusahamad6724 6 ปีที่แล้ว +1

    what if input is not {0,1}??

  • @sandhyakapil
    @sandhyakapil 4 ปีที่แล้ว

    Excellent !!! Thank you so much !!

  • @thedaylightpodcast
    @thedaylightpodcast 5 ปีที่แล้ว +1

    Thank you! This was really helpfull.

  • @nalinsharma9881
    @nalinsharma9881 7 ปีที่แล้ว +12

    I think there is a correction : transition function for NFA should be QxSigma -> PowerSet(Q)......not 2^Q

    • @nalinsharma9881
      @nalinsharma9881 7 ปีที่แล้ว

      Neso Academy: yup thanks...just wanted to mention it.....even I won't forget it now ever.

    • @hausmeisterkraftfahr
      @hausmeisterkraftfahr 6 ปีที่แล้ว +3

      it is true that the power set contains 2^Q elements, but you can't define a function the way you did in this video. nalin sharma is right with his objection. other than that, great channel and great work, my man.

    • @koustavchoudhury5833
      @koustavchoudhury5833 6 ปีที่แล้ว

      Yes nalin sharma made a valid point. When you are defining a mapping it should always be from one set to another set.

    • @NavalKishoreBarthwal
      @NavalKishoreBarthwal 6 ปีที่แล้ว +1

      @Neso I think correct version should be (cardinality of alphabets) raise to the power (number of states)

    • @kasozivincent107
      @kasozivincent107 4 ปีที่แล้ว

      But 2^Q is the powerset of Q. Try to check with sets and see.

  • @CodeTechGyan
    @CodeTechGyan 3 ปีที่แล้ว

    Sir is any NFA diagram possible without start state given?

  • @NoName-jy4cv
    @NoName-jy4cv 3 ปีที่แล้ว

    Thank you!

  • @rochishnumajumder5439
    @rochishnumajumder5439 4 ปีที่แล้ว +5

    Sir I have 3 questions regarding this particular lecture video:-
    1. Does NFA belong to the category of Finite State Machines?
    2. So can we conclude that NFA does not have the concept of a dead state as we saw in DFA?
    3. Regarding the 5th tuple of NFA (i.e. delta) sir, will it not be more specific to say that 'Q × sigma = sigma ^ Q' instead of just saying 'Q × sigma = 2^Q' ?
    Sir because, it might be possible that there are 3 or 4 or let's say 'sigma' number of input symbols in the NFA.
    For e.g. : The input symbols may be 0, 1,2,3,4. Then we have 5 input symbols,.... So it should be 'Q × sigma = 5 ^ Q'.
    Sir please answer these 3 questions of mine....
    Otherwise your lectures are very helpful for clearing my concepts, and making me understand the concepts in an easy manner.😊👍

    • @utkuarslan5
      @utkuarslan5 4 ปีที่แล้ว +4

      Rochishnu Majumder_2H_46 hey dude, i can answer your 3rd question. it’s always Q x sigma = 2^Q’ because every symbol can always be represented in binary(1,0) form. computational machines (computers), going from one state to another is O(1) constant time. Thereby, whenever you have a symbol that's not 1 or 0, you convert it into binary representation and process that version. That's why it's always two to the power.

    • @MMNayem-dq4kd
      @MMNayem-dq4kd ปีที่แล้ว

      1)Yes
      2)No
      3)No

  • @muhammadashfaq8032
    @muhammadashfaq8032 2 ปีที่แล้ว

    Which is best book for automata theory

  • @kylesaunders8029
    @kylesaunders8029 2 ปีที่แล้ว +2

    more formally it should be 2^|Q| meaning the cardinality of Q

  • @Amarsingh-mr7zc
    @Amarsingh-mr7zc 5 ปีที่แล้ว

    In formal defination on nfa how did u assumed power like 2 to the 2 or 2 to the power 3?

  • @kainaatmakhani6550
    @kainaatmakhani6550 2 ปีที่แล้ว

    good lecture

  • @naveenkumarkalagarla5713
    @naveenkumarkalagarla5713 3 ปีที่แล้ว

    in the video, for NFA can we say del: Q x sigma --> Q*?

    • @debosmitachatterjee1096
      @debosmitachatterjee1096 3 ปีที่แล้ว

      Q* is an infinite set . You can repeat the single input as many times as you want but in case of delta this is definitely not the case. So I guess it will not be correct.

  • @mahakaal555
    @mahakaal555 2 ปีที่แล้ว

    If there will be notes,it will become easy to understand after watching videos.

  • @anuthomas183
    @anuthomas183 3 ปีที่แล้ว

    Thank you sir

  • @TheSrilathareddy
    @TheSrilathareddy 7 ปีที่แล้ว

    Very good explanation

  • @nasiruumar690
    @nasiruumar690 5 ปีที่แล้ว

    Very helpful sir

  • @hdm_vision
    @hdm_vision 6 ปีที่แล้ว

    What makes A have possibilities to go to no where ????

  • @kasozivincent107
    @kasozivincent107 4 ปีที่แล้ว +1

    You forgot one important thing when discussing the transition function delta. since we have a possibility of upsilon as an input, u have to re define the domain of the function from SigmaXQ to Sigma X (Q U upsilon) -> 2^Q

    • @Shivani-pe7rv
      @Shivani-pe7rv 4 ปีที่แล้ว +1

      shouldn't it be Q X (Sigma U upsilon) -> 2^Q

  • @fanhsp9294
    @fanhsp9294 5 ปีที่แล้ว +5

    i think QxΣ is wrong cause in nfa we can have also ε as transition to a state..thanks for the videos 😊

  • @TheSrilathareddy
    @TheSrilathareddy 7 ปีที่แล้ว

    Can you make a video on extended transition function of DFA

  • @blakefeucht960
    @blakefeucht960 6 ปีที่แล้ว +1

    Wouldn't it be more correct to say 2^|Q|?

  • @alamzeb3359
    @alamzeb3359 6 ปีที่แล้ว

    PERFECT SIR..........

  • @احمدكريم-ل4ف8ي
    @احمدكريم-ل4ف8ي 6 ปีที่แล้ว

    thank you very much

  • @brownchocohuman6595
    @brownchocohuman6595 4 ปีที่แล้ว

    I remember when he told about dead state in a previous lecture, many "geniuses" were calling him wrong :)

  • @EasyH4ck
    @EasyH4ck 3 ปีที่แล้ว

    Hi, I have question about the transaction function, if the | Q x Segma => 2^Q | in this formula, the Q is the number of state but 2 represent what ? because it's just similar to say | Q x Segma => P(Q) | so i need to recognize what 2 means in this formula and thanks for those nice courses ^^

    • @deviprasanna2551
      @deviprasanna2551 3 ปีที่แล้ว +1

      in this formula 2 means inputs(sigma)

  • @SHUBHAMSHARMA-fc9ny
    @SHUBHAMSHARMA-fc9ny ปีที่แล้ว

    does it contains all the topics

  • @AhamedKabeer-wn1jb
    @AhamedKabeer-wn1jb 4 ปีที่แล้ว

    Thank you..

  • @HIMANSHU_961
    @HIMANSHU_961 3 ปีที่แล้ว

    really wonderfull

  • @dhanushsivajaya1356
    @dhanushsivajaya1356 4 ปีที่แล้ว

    Thankyou sir

  • @loadedbylarry
    @loadedbylarry 4 ปีที่แล้ว

    nice video!!

  • @chabotaluputa7665
    @chabotaluputa7665 8 หลายเดือนก่อน

    Amazing....

    • @swapnilmane2537
      @swapnilmane2537 8 หลายเดือนก่อน

      U must be a student of SRTMU NANDED

  • @SKumar-ur9tz
    @SKumar-ur9tz 4 ปีที่แล้ว +1

    The range should be (sigma) Q^i for all i

  • @apporvaarya
    @apporvaarya 5 ปีที่แล้ว

    need more examples to understand it

  • @storkay1
    @storkay1 7 ปีที่แล้ว +4

    at 7:20 you said for various inputs to A the possible outcomes are A,B,AB, phi
    but if u consider the input set A,B both of them already have their own values, then why mention phi for A.
    if A needs an output phi you need to consider something out of the input-set,which you should'nt do.
    SO i see no proper reason for including phi in ur explanation

    • @Harshal102
      @Harshal102 6 ปีที่แล้ว

      Did you find the explanation of this? Please tell.

    • @abdulwasaykhan6438
      @abdulwasaykhan6438 6 ปีที่แล้ว

      May be phi can come only if it gets 1 as input and never gets input 0, in that case phi will be correct for A as it doesn't reach the other state which is B. I may be wrong but I got confused on that too.

    • @aydict
      @aydict 6 ปีที่แล้ว

      Phi means 'nothing', so you can include it as an output for any state in NFA

    • @vivekthakur1953
      @vivekthakur1953 5 ปีที่แล้ว

      what if it has 3 inputs and A on the 3rd input goes to phi

  • @LadderVictims
    @LadderVictims 10 หลายเดือนก่อน

    There are only 2 power Q states possible so Q x E can map to only these possible states.

  • @shinigamiryuk4183
    @shinigamiryuk4183 3 ปีที่แล้ว

    my teacher plays your videos in lectures

  • @Mr-Producer.
    @Mr-Producer. 7 ปีที่แล้ว

    How come it goes AB A,B are different states right how come you combine them?

    • @handleh
      @handleh 6 ปีที่แล้ว

      It means for that ip it goes to both the states

    • @siya847
      @siya847 3 ปีที่แล้ว

      thank you. was searching for this question :)

  • @kanishkrawat277
    @kanishkrawat277 7 ปีที่แล้ว

    please upload all the lectures sir
    .. exams are going to start soon 16th may

  • @MathComputerScienceTradi-ge7tw
    @MathComputerScienceTradi-ge7tw 10 หลายเดือนก่อน

    What does del* stand for?

    • @Dodge_170
      @Dodge_170 10 หลายเดือนก่อน

      Transition function

  • @boblewis1287
    @boblewis1287 3 ปีที่แล้ว

    How do go to phi

  • @ezioauditore007100
    @ezioauditore007100 6 ปีที่แล้ว

    cant we just say that, qxe maps to the power set of q?

  • @donplay4307
    @donplay4307 3 ปีที่แล้ว

    it should be power set of Q

  • @anukumari7088
    @anukumari7088 5 ปีที่แล้ว

    Sir B pr transition 0 nhi aaega

  • @mohammadmansour9390
    @mohammadmansour9390 3 ปีที่แล้ว

    perfect

  • @8089525315
    @8089525315 8 ปีที่แล้ว

    Thanks