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}}
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.
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?
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?
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
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.
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.
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?
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.
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.
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.
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
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 ^^
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
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.
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
my friend had studied from your videos, he passed
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
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
Love love love your explanations, never felt this confident about TOC before!!!
Вы так доходчиво объсняете! 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.
man I love your channel. When i graduate and work one day I'm gonna come back here and make a big contribution.
Did you graduate?
bro you got job ?
9:21 it maps to (cardinality of alphabets) raise to the power (number of states)
Thanks!
Thank you. Your lectures are very easy to understand and it helped me a lot. Keep up your good work.
timro videos easy to understand hoyo.. molai samjh ma ayo daju! Thank you so much❤️
This series of lectures of Finite automata are very helpful
sir clear expalnation and byed d bay the mucic while starting of the video is awesome
raise your hand if anyone is speed running this at 2x speed one day before the exam
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 for the fantastic tutorial. It's very helpful.
Please you have any notes
I don't trust college. I'm doing my engineering from here. Thank you. You are a great teacher.
HaHahaaaaa
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?
I freaken love you and this channel for this content!
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
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?
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
at 5:14 B should be {B}
you saved my life, thank you so much
Thank you very much!! Really Helpful!
-From India
Lol, this channel belongs to an Indian only!!
What a topic thanks to Neso academy
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.
Tanks for amazing lessons
You are simply the best
Please do a video on complete and non complete that baffled ne all these years
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
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.
i like your explanation about this course
Why A after getting input 1 will go nowhere? Confused...... 7:10
TNX a lot Sir, How A by 1 can goes to B?
THANK YOU for uploading this topic...it helped me alot. thanks sir ...
Sir please upload network security videos
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?
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)
You are the best 😊
Thankyou !!
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!
You are a legend.
What happens when nfa final state could get a input?
Thank you.. Well explained..
For those wondering why is it 2^Q, it is because nC0 + nC1 + nC2 + ... + nCn = 2^n
I understand the combination formula, but don't get how fro state A went to state Fi when ita not drawn as possible...
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
I don’t get how,there are possibilities to go any state if there is no transition between them ?
Thank you 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
Sir please keep up the videos Sir!We are a strong team together!!
It's really helpful
Fenomenal!
what if input is not {0,1}??
Excellent !!! Thank you so much !!
Please you have any notes
Thank you! This was really helpfull.
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.
Sir is any NFA diagram possible without start state given?
Thank you!
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
Which is best book for automata theory
more formally it should be 2^|Q| meaning the cardinality of Q
In formal defination on nfa how did u assumed power like 2 to the 2 or 2 to the power 3?
good lecture
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.
If there will be notes,it will become easy to understand after watching videos.
Thank you sir
Very good explanation
Very helpful sir
What makes A have possibilities to go to no where ????
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
i think QxΣ is wrong cause in nfa we can have also ε as transition to a state..thanks for the videos 😊
Can you make a video on extended transition function of DFA
Wouldn't it be more correct to say 2^|Q|?
PERFECT SIR..........
thank you very much
I remember when he told about dead state in a previous lecture, many "geniuses" were calling him wrong :)
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 ^^
in this formula 2 means inputs(sigma)
does it contains all the topics
Thank you..
really wonderfull
Thankyou sir
nice video!!
Amazing....
U must be a student of SRTMU NANDED
The range should be (sigma) Q^i for all i
need more examples to understand it
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
Did you find the explanation of this? Please tell.
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.
Phi means 'nothing', so you can include it as an output for any state in NFA
what if it has 3 inputs and A on the 3rd input goes to phi
There are only 2 power Q states possible so Q x E can map to only these possible states.
my teacher plays your videos in lectures
How come it goes AB A,B are different states right how come you combine them?
It means for that ip it goes to both the states
thank you. was searching for this question :)
please upload all the lectures sir
.. exams are going to start soon 16th may
What does del* stand for?
Transition function
How do go to phi
cant we just say that, qxe maps to the power set of q?
it should be power set of Q
Sir B pr transition 0 nhi aaega
perfect
Thanks