Formal Definition of Non-Deterministic Finite Automata (NFA)
ฝัง
- เผยแพร่เมื่อ 25 ส.ค. 2024
- TOC: The formal definition of non-deterministic finite automata.
Topics discussed:
In this lecture, the formal definition of NFA is given and each of the tuples is explained with the special focus on the transition function.
Full Course on TOC: goo.gl/f4CmJw
Follow Neso Academy on Instagram: @nesoacademy (bit.ly/2XP63OE)
Follow me on Instagram: @jaiz_itech (bit.ly/2M3xyOa)
Contribute: www.nesoacademy...
Memberships: bit.ly/2U7YSPI
Books: www.nesoacademy...
Website ► www.nesoacademy...
Forum ► forum.nesoacad...
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
#TheoryOfComputation #TOCByNeso #NFA #DefinitionOfNFA #AutomataTheory
![ถามตรงๆ กับ อาจตุพร ทำไม ประเทศไทย ใครเป็นนายก ก็โดนด่า พอออกเเล้วคนคิดถึง!!?? l [Nickynachat]](http://i.ytimg.com/vi/3YFLMXxBGAs/mqdefault.jpg)
I have seen all lectures....It's wonderful. Got highest in the last semester.
Damn bro
Same Really helpful brother ....💞💝
If you made any notes can you please send me the drive link, it'll help a lot 🙏
From which book Or from which online source you pratice
Wasted my 2 hrs in class. Should have watched this instead. This series is very nice. Love you sir.
fr man
Never attended my lectures after watching this. I aced my exams for this subject.
Wasted a whole semester!
class made this subject a boring one
@@ashleynjeri.n. 😂😂😂Njeri enda class
You're such a legend. Exam tomorrow... learned more in 2 hours of vidoes than 2 months of uni. Tytyty
man I love your channel. When i graduate and work one day I'm gonna come back here and make a big contribution.
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}}
Cheers, this confused me for a long time.
Oh thanks, I didn't know this was a notation. I was about to leave a comment about that lmao
raise your hand if anyone is speed running this at 2x speed one day before the exam
Вы так доходчиво объсняете! 3 года ваши лекции выручили на первом курсе, и сейчас, на четвертом, вы меня снова спасаете! от всей души благодарю!!!
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.
Love love love your explanations, never felt this confident about TOC before!!!
timro videos easy to understand hoyo.. molai samjh ma ayo daju! Thank you so much❤️
these are so much better at 1.5 speed
Bread *1.25x
2 Speed :)
I think in 2.0 speed is much more better :))
Not for us dumb people, it isn't
1.75 :)
Thank you. Your lectures are very easy to understand and it helped me a lot. Keep up your good work.
This series of lectures of Finite automata are very helpful
I don't trust college. I'm doing my engineering from here. Thank you. You are a great teacher.
HaHahaaaaa
sir clear expalnation and byed d bay the mucic while starting of the video is awesome
THANK YOU for uploading this topic...it helped me alot. thanks sir ...
Thank you for the fantastic tutorial. It's very helpful.
Please you have any notes
9:21 it maps to (cardinality of alphabets) raise to the power (number of states)
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?
Tanks for amazing lessons
I freaken love you and this channel for this content!
What a topic thanks to Neso academy
you saved my life, thank you so much
Thank you very much!! Really Helpful!
-From India
Lol, this channel belongs to an Indian only!!
Please do a video on complete and non complete that baffled ne all these years
Sir please upload network security videos
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
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?
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?
You are simply the best
i like your explanation about this course
at 5:14 B should be {B}
You are the best 😊
Thank you.. Well explained..
good lecture
more formally it should be 2^|Q| meaning the cardinality of Q
Thank you! This was really helpfull.
If there will be notes,it will become easy to understand after watching videos.
For those wondering why is it 2^Q, it is because nC0 + nC1 + nC2 + ... + nCn = 2^n
I remember when he told about dead state in a previous lecture, many "geniuses" were calling him wrong :)
Thanks!
Sir please keep up the videos Sir!We are a strong team together!!
I was thinking instead that it maps it to the power set of Q
d : Q × E ---> P(Q)
What do you think
Quite right. DFA maps to Q and nfa to 2^Q.
By the way nfa is Q×(E U {€}) --> P(Q)
It's really helpful
Excellent !!! Thank you so much !!
Please you have any notes
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.😊👍
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.
1)Yes
2)No
3)No
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.
Thank you sir❤️
Fenomenal!
Very good explanation
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
shouldn't it be Q X (Sigma U upsilon) -> 2^Q
Very helpful sir
Thanku so much . My doubt is cleared that why the transition function maps to 2^Q.
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..':)
@@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
Thank you!
Thank you sir
thank you very much
PERFECT SIR..........
Thank you..
really wonderfull
I understand the combination formula, but don't get how fro state A went to state Fi when ita not drawn as possible...
TNX a lot Sir, How A by 1 can goes to B?
i think QxΣ is wrong cause in nfa we can have also ε as transition to a state..thanks for the videos 😊
Thankyou sir
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.
You are right. Do have some issues, but still a wonderful and best autamata course.
6:47 how does A ( a certain input) ever gives phi (nowhere)? you mean it could ultimately give phi, after also going through B?
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
it should be power set of Q
Why A after getting input 1 will go nowhere? Confused...... 7:10
The range should be (sigma) Q^i for all i
I think there is a correction : transition function for NFA should be QxSigma -> PowerSet(Q)......not 2^Q
Neso Academy: yup thanks...just wanted to mention it.....even I won't forget it now ever.
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.
Yes nalin sharma made a valid point. When you are defining a mapping it should always be from one set to another set.
@Neso I think correct version should be (cardinality of alphabets) raise to the power (number of states)
But 2^Q is the powerset of Q. Try to check with sets and see.
Which is best book for automata theory
Can you make a video on extended transition function of DFA
nice video!!
What happens when nfa final state could get a input?
waw gaice it is very nice learining
please upload all the lectures sir
.. exams are going to start soon 16th may
Thanks
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.
it happens when the function is not necessarily well defined, it is just a relation!
how can giving 1 to A result in going to AB at 7:25 ?
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?
@@eldqvist how null is considered as state,could you elaborate it?
@@prashanthi8492 it's an NFA = Non Deterministic, so null can be a state, same as multiple paths can be taken
@@eldqvist yeah I understood after watching full , anyways thanks
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?
perfect
my teacher plays your videos in lectures
need more examples to understand it
Just want to clarify that at the end you said
Q x Sigma --> 2^Q
Where 2 happens to be cardinality of sigma.
Now what of sigma had 4 or 5 elements? I guess it then becomes
Q x Sigma -> (cardinality of sigma)^ Q
what if input is not {0,1}??
There are only 2 power Q states possible so Q x E can map to only these possible states.
does it contains all the topics
In formal defination on nfa how did u assumed power like 2 to the 2 or 2 to the power 3?
Wouldn't it be more correct to say 2^|Q|?
Super
Sir is any NFA diagram possible without start state given?
At 8:19, how can move from A to Ø with input 1?
How do go to phi
What makes A have possibilities to go to no where ????
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,..
sir said " 'A' on getting a certain input" not 1, although he writes 1 there
I think it's a "i" for "input", not a "1". It's a generalization.
@@matheusassis6601 Yes, I can see a small dot there. it's an i for any input
in the video, for NFA can we say del: Q x sigma --> Q*?
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.
tq u sooo much😅😅😅😅💗💟
"breaking bad" serial background music
if i am wrong please you explain again through other vedio
please sir
won't the formula be E^Q instead of 2^Q
The instructor in our class spend an hour to teach and provide one example which is boring, that why i prefer here more compact and direct explanation.
People just lov to say s**t abt youtub videos, atleast he shared wht he knows, geniuses just know how to criticize!