Answer to Assignment at 08:16 Ex 1 : 2 States (A is Starting State, A on 1 goes to B, A on 0 stays in A, B is Final State, B on 1 stays in B, B on 0 goes to A) Ex 2 : 2 States (A is Starting State, A on 1 stays in A, A on 0 goes to B, B is Final State, B on 0,1 stays in B) Ex 3 : 4 States (A is Starting State, A on 1 goes to B, A on 0 goes to D, D is Dead State, B on 1 goes to D, B on 0 goes to C, C is Final State, C on 0,1 stays in C) Ex 4 : 3 States (A is Starting State, A on 0 goes to B, A on 1 stays in A, B on 1 goes to C, C is Final State, B on 0 stays in B, C on 0,1 stays in C) Ex 5 : 3 States (A is Starting State, A on 0 stays in A, A on 1 goes to B, B on 1 goes to C, C is Final State, B on 0 goes to A, C on 0,1 goes to A)
@@lonlyyfans Hey, but in the question they said they should only contain "01" , so if you assume 10010 will not be accepted even though your string is valid, so rajesh answer is true.
Great work brother ✨.... But in ex 5 C on 1 should go to C as we want a string which should end with '11' so it doesn't matter that at end how many 1's occur as example like 110111 will not be accepted if we take your solution to consideration.
@@pranaygupta5845 There is something like 75% minimum attendance in India according to my family there, but here in Portugal, and in many other countries, the only thing that matters is your scores in tests/exams and projects.
@@gauravghosh6562 i think you added a dead state at the end which is incorrect because 011011 is also valid so for the final state if 0 is encountered jump to initial state if 1 is encountered give it a self loop at the final state cause 01111 is also accepted
Thank you.. You are like our life savior.. Really!!! Thank you so much.. Tomorrow is my sem. Xam.. And m watching it really faster.. I hope I could get all my CS subjects taught by you.. You are really our life savior.. Thank you..
hei do you know how to solve this? Design a Non-deterministic Finite Automata (NFA) for the syntax of the chosen construct. Note that the NFA must cover the generic syntax of the construct, and not be limited to just a specific sample code. The syntax covers all valid code for the construct, hence the NFA must accept all valid code, whilst rejecting all invalid code.
NOTE: Example 4: Upon getting input "0" at state B, it should go to state B and not "phi". Therefore, a self-loop at B for input "0" is required. The self-loop at A for input "0" is redundant. Also, the self-loop at B is required only when the self-loop at A is removed. Example 5: Upon getting input "0" at state B, it should go to state A and not "phi". Self-loop at A for input "1" is not redundant. Solve for string 111, you will understand why the self-loop is required. Also, B should go to state A at input "0" only when the self-loop at A for "1" is removed.
It works fine for 111. See, there are 2 ways first for A(A,B). Then for A(A,B), for B(C,phi). Again for A(A,B), for B(C). There, you've reached state C for 111. Hope you get my point :)(A->A->B->C)
example 4 : i think at b state it goes like this (b,1)->c and (b,0)->a try with eg 00101 with both nfa's example 5 : also in this example at b state (b,0)->a and (b,1)->c and at c state also (c,1)->c and (c,0)-> phi try to validate this with example 01011011
In example four it makes more sense if A does not go back to itself when '0' is the input. Rather, move to state B and in state B if another '0' is inputted stay in state B.
I'm glad someone else thought this to be problematic as well. The way it's stated in the video, one would think that final state C could never be reached if 0 is input at state B.
That's why it is called NFA because one input can have many states Also the problem says that it should contain with 01 so their can be any number of string symbols before 01 comes and it can be done both ways.. with loop to A itself or move to B
My answer for assignment: (i) 3States (ii) 2 states (iii) 5 states (iv) 3 states (v) 3 states. Thanks for the lectures. Very easy to understand and doesn't get bore at all.
(i) 2 States (A0A, A1B, B0A, B1B, with B as final state). And (iii) 4 States (A0D, A1B, B0C, B1D, C0C, C1C, D0D, D1D, with C as final state and D as a trap state).
At 6:48, why we are not looping the zero to B again, because 001 will also be selected by the machine, but acc. To your NFA, if 00 comes, it'll go to fi after B
ik this comment is 2 years old, but for anyone curious, it's bc it's nfa. it's possible to run the machine such that the first 0 goes back to A and the second 0 goes to B. no need to find alternative ways to run the machine, when you've confirmed that at least one way is accepted. as mentioned in the nfa solved example 1, "If there is any way to run the machine that ends in any set of states out of which at least one state is a final state, then the nfa accepts".
I think most people have a doubt in L4 where you are saying that shouldn't B self-loop in 0, the answer is no because there will be a path where 0's will get looped in A. For eg in 10001, path can be A->A->A->A->B->C
yep even I felt the same, in the 1st example where we have to construct an NFA that accepts string that end with 1, in the final state probably we could just give a self loop(i.e on accepting 1 the state b stays in the final state) I guess even that's right.
why can't we restrict the self loop on A to only 1 instead of 0,1? Because if one 0 is encountered then it will jump to the final state and that should work fine .
@mansharkpig The point of the machine is to detect the occurrence of the zero and not it's position right? I think the instructor has drawn the diagram just to reinforce the concept of an NFA. A simple DFA would work fine as well.
DFAs : a) L1 = = Minimum 2 states ( All strings that end with '1' ) b) L2 = Minimum 2 states ( All strings that contain '0' ) c) L3 = Minimum 3 states, 1 dead state ( All strings that start with '10' ) d) L4 = Minimum 3 states ( All strings that contain '01' ) e) L5 = Minimum 3 states ( All strings that end with '11' ) I checked all possible strings and All are accepted. And all invalid strings are not accepted.
@@ranggagumilang7890l3 have dead state because if we get 0 I/p at starting where it will go and l5 doesn't have it because it has loop to keep it in self
In EX 2) why is there a 0 from state A to state A? It should not have a 0 from state A to state A since on a string containing 0 it should go to the final state B?
Hello, in example 2 can we remove input 0 for self loop to first state A and only keep input 1 because it says that the strings should contain zero. So if we get zero input even once we can transition to final state?
As far as the question is concerned i guess u r right and what he did is the case when the string is having more than one zeros. But also it is not told in the question if the string could contain one or more than one zeros, so his case also pretty well satisfies the condition.
Considering the requirements of the language , His Automata is inefficient considering time, it may take too long before we know if the language is accepted by the AUTOMATA
In example 2 on giving input 0 on state A there should be only one transiotion from A to B only ,as after getting 0 as input we go on final state only.
I think for L2, redirecting the state to A on zero is redundant, since if the number starts with zero and has any thing after that it will eventually end up in state B, kindly correct me if I am wrong though
@@prajwalp8070 why tho? trying 1001011 works fine without A pointing to itself. Because once there is a 0, it should just go to the final state B. Because it means the string contains 0, which is what we need.
@@mehulsingh1216 no bro it is not but what is mandatory is for all the states to know where to go with certain inputs we might not need a dead state sometimes
I think Neso just give construct which is prone to have branches when he construct the NFA (Which may add unnecessary confusion). I think it is better to construct the necessary step first is more easy to understand. Neso do enlighten me, thanks~
That's correct but it is an nfa...so it can any possible ways... it just our wish and thinking...if want more possible way..we can add self loop anywhere..it's not an error 😁✨
L1- 2 states L2- 2 states L3- 4 states ( one state for dead state) We need one extra state for dead state if condition says strings starting with “substring”.ie n+1+1(dead state) here n is length of substring, in this example it’s 10 so n is 2.. total number of states=2+1+1=4 L4- 3 states L5- 3 states
@Rishika Garg there is clearly specified that the string should contain '01' so you can not put self loop on B because there after maybe it won't contain exact '01' in it.. and in the 5th example, there is no need to have transition of 0 from B to A because it is a NFA.. in NFA u don't need to specify dead state or any other extra transition of input..
@@siddhanthallan2259 We do not need to counter every possible input, '001' will be tackled when A loops back to itself on the first '0' and then proceeds to B and C on the next '0' and '1'. In NFA we just need to make 1 such path that will surely reach final state, it can still have multiple dead paths. Hope this helped.
Right, In the 4th, I think A should have a self-loop of just 1, B should have a self-loop of 0 and all others stay the same should be a better solution
example 4 : i think at b state it goes like this (b,1)->c and (b,0)->a try with eg 00101 with both nfa's example 5 : also in this example at b state (b,0)->a and (b,1)->c and at c state also (c,1)->c and (c,0)-> phi try to validate this with example 01011011 correct me if i am wrong
No, in NFAs you only mention transition states and self loop at the starting or ending depending whether the asked patter is in start (then self loop at end), in the end (then self loop at the beginning), in between (then self loop at the start as well as at the end)
sir, in example 4.If we want to accept the string 001,how how the NFA will accept?Explanation:present we are at A and if 0->B,now we are at B and if we again take 0 then where we will go???..if nothing is there we assume it to dead configuration ,right?..so how the 001 is accepted??
See ,in nfa u have to see all the possible outcomes of a string being given as an input and if atleast 1 of them leads to final state ,then the string is accepted. So for string 001 :::: A -> B -> C ,this way gets us to final state hence it is accepted
@@Eswarsai245 no ,if 0 is given as input on b it can't go to c.. But in 001, the first 0 can change the state from A to A due to the self loop,.. ,second 0 :A to B.., then 1:B to C.... this is 1 of the possible configurations and it gets us to final state. Thus it is accepted even if the other paths cannot make us reach the final state. Hope it helps.:)
according to me in example 2 there is no need of giving input 0 for self loop to first state A and only keep input 1 because it says that the strings should contain zero. So if we get zero input even once we can do the transition to final state . e.g. if i get 11101 here as soon as i got 0 , the string can now be accepted , i understand there can be more than one next step for each state , but that next step should make sense. if on getting first 0 , i keep it in state A only , then on taking the self loop it stays in state A only and would not be accepted .
@@friendsitcom2312 to my eyes, it is already a NFA without the self loop on A . I think we don't need that self loop to make it NFA. As it is not defined where the State transitions on getting input one.
Incorrect. You are giving an example of 010, but you are not accounting for ALL possible 01 combinations. You need the loop to illustrate that there are an infinite number of solutions as long as the sequence of 01... is continued.
Wouldn't the first example (set of string ends in 1) be wrong? As I understand, NFA can move both ways so a "010" string would move to the final state when it get to "1". Is it because the final can be considered a dead state (ie. in the case of "010", when the NFA reach the last "0" the NFA would reject the input)?
When you take the example 010, so the machine is made to reject this string cause it doesn't ends with 1..... The example is correct maybe you need to watch that part again...
Example 5, I think there'll be one more transition from State B to State A, because consider 1011 as a string, it wont get accepted as it would end up on the 'phi' state
Assignment Answer L1, L2, L4 & L5 have same states as NFA except L3 - 4 states Btw you are a great teacher Please write your name if you see this comment Thank you 😊
In example first considering string 1101, why transition doesn't go to state B when input is 1 and to dead configuration.How compiler know about which state to go when input is 1 since when there is input 1 in state A ,transition can go either state A or B.If it goes to state B how such strings are accepted?? Please answer it.
how will the machine decide if by getting 1st 0 it should remain on a or move to b . as by opting the latter if it again encounters 0 it will go to dead or fi state
Very good video, sometimes the professor go through things too quick, this video helped me a lot, I could pause and have time to understand the material
@@AmineZyad i think 3 states because in case if we get 0 in example#1 so it will go to dead or trap state so if we count all states so,it will be 3 states.
How can machine decide which state to go if there are more than 1 possibility on getting input??Like in L5 if it gets input 1 either it goes to A itself or B as well.For input 11, If it goes to A on getting input-1 and again goes to A on getting input-1,It will never reach final state and it becomes wrong NFA. Can anyone clarifies this...
Answer to Assignment at 08:16
Ex 1 : 2 States (A is Starting State, A on 1 goes to B, A on 0 stays in A, B is Final State, B on 1 stays in B, B on 0 goes to A)
Ex 2 : 2 States (A is Starting State, A on 1 stays in A, A on 0 goes to B, B is Final State, B on 0,1 stays in B)
Ex 3 : 4 States (A is Starting State, A on 1 goes to B, A on 0 goes to D, D is Dead State, B on 1 goes to D, B on 0 goes to C, C is Final State, C on 0,1 stays in C)
Ex 4 : 3 States (A is Starting State, A on 0 goes to B, A on 1 stays in A, B on 1 goes to C, C is Final State, B on 0 stays in B, C on 0,1 stays in C)
Ex 5 : 3 States (A is Starting State, A on 0 stays in A, A on 1 goes to B, B on 1 goes to C, C is Final State, B on 0 goes to A, C on 0,1 goes to A)
In ex 4 C on 1 should go to C (self loop) and C on 0 should go to B no?
@@lonlyyfans Hey, but in the question they said they should only contain "01" , so if you assume 10010 will not be accepted even though your string is valid, so rajesh answer is true.
In ex 5, C on 1 should go to C
@@dimitriskk3613exactly
Great work brother ✨.... But in ex 5 C on 1 should go to C as we want a string which should end with '11' so it doesn't matter that at end how many 1's occur as example like 110111 will not be accepted if we take your solution to consideration.
Thanks Neso academy for clear cut videos you don't know how many students u have saved from head aches Tq Neso and the Sir💙
Neso makes me feel like deactivating my ad blocker when I watch all his videos
Lol but you don't
I did bro, at least if I am not donating, I would not stop them from video monetization.
i turned down the brave shield, because the quality of content given by neso is just out of the room.
But the time remaining for my exam makes me not do it
literally i bought yt premium at the last video
i swear
Didn't show up to my Theory of Computation class in 3 weeks and your lectures got me a 92/100 on the test.
Weren't you detained for not attending classes that long?
@@pranaygupta5845 In the United States, some classes don't care about attendance
@@pranaygupta5845 There is something like 75% minimum attendance in India according to my family there, but here in Portugal, and in many other countries, the only thing that matters is your scores in tests/exams and projects.
@@chrisrey2516 OK you are telling that you're in USA..,
@@monstercoder3665 so what ?
Thanks!
According to DFA:
a) 2 states
b) 2 states
c) 4states( one state will be dead or trap state)
d) 3 states
e) 3 states
Shi ho aap 👍
e) i think will have 4 states ( 3 +1 dead)
@@gauravghosh6562 i think you added a dead state at the end which is incorrect because 011011 is also valid so for the final state if 0 is encountered jump to initial state if 1 is encountered give it a self loop at the final state cause 01111 is also accepted
@@gauravghosh6562 yes
@@w1ch3r29 You're correct!
Thank you.. You are like our life savior.. Really!!! Thank you so much.. Tomorrow is my sem. Xam.. And m watching it really faster..
I hope I could get all my CS subjects taught by you.. You are really our life savior.. Thank you..
hei do you know how to solve this?
Design a Non-deterministic Finite Automata (NFA) for the syntax of the chosen construct. Note that the NFA must cover the generic syntax of the construct, and not be limited to just a specific sample code. The syntax covers all valid code for the construct, hence the NFA must accept all valid code, whilst rejecting all invalid code.
@@chandra-hx2cw hey, did you find the answer to this?
NOTE:
Example 4:
Upon getting input "0" at state B, it should go to state B and not "phi". Therefore, a self-loop at B for input "0" is required. The self-loop at A for input "0" is redundant. Also, the self-loop at B is required only when the self-loop at A is removed.
Example 5:
Upon getting input "0" at state B, it should go to state A and not "phi". Self-loop at A for input "1" is not redundant. Solve for string 111, you will understand why the self-loop is required. Also, B should go to state A at input "0" only when the self-loop at A for "1" is removed.
It works fine for 111. See, there are 2 ways first for A(A,B). Then for A(A,B), for B(C,phi). Again for A(A,B), for B(C). There, you've reached state C for 111. Hope you get my point :)(A->A->B->C)
@@druthi9700 ig he was mentioning the DFA for the respective NFA, in that case his points are valid.
@@shauryaverma292 i dont think he meant those for DFA, because DFA does not allow 'phi'
example 4 : i think at b state it goes like this (b,1)->c and (b,0)->a try with eg 00101 with both nfa's
example 5 : also in this example at b state (b,0)->a and (b,1)->c and at c state also (c,1)->c and (c,0)-> phi try to validate this with example 01011011
In example four it makes more sense if A does not go back to itself when '0' is the input. Rather, move to state B and in state B if another '0' is inputted stay in state B.
I'm glad someone else thought this to be problematic as well. The way it's stated in the video, one would think that final state C could never be reached if 0 is input at state B.
That's why it is called NFA
because one input can have many states
Also the problem says that it should contain with 01 so their can be any number of string symbols before 01 comes and it can be done both ways.. with loop to A itself or move to B
My answer for assignment: (i) 3States (ii) 2 states (iii) 5 states (iv) 3 states (v) 3 states.
Thanks for the lectures. Very easy to understand and doesn't get bore at all.
(i) 2 States (A0A, A1B, B0A, B1B, with B as final state). And (iii) 4 States (A0D, A1B, B0C, B1D, C0C, C1C, D0D, D1D, with C as final state and D as a trap state).
correction *
1>2states, 2> 2 states ,3> 4states ,4> 3 state ,5> 3 state
@@AyanKhan-fe4qc 5 ka 4 state hoga ends with 11 bola hai .. toh agr 0 pe end hua tb toh dead state mei chla jayega na
At 6:48, why we are not looping the zero to B again, because 001 will also be selected by the machine, but acc. To your NFA, if 00 comes, it'll go to fi after B
ik this comment is 2 years old, but for anyone curious, it's bc it's nfa. it's possible to run the machine such that the first 0 goes back to A and the second 0 goes to B. no need to find alternative ways to run the machine, when you've confirmed that at least one way is accepted.
as mentioned in the nfa solved example 1, "If there is any way to run the machine that ends in any set of states out of which at least one state is a final state, then the nfa accepts".
Neso.........is the best
I think most people have a doubt in L4 where you are saying that shouldn't B self-loop in 0, the answer is no because there will be a path where 0's will get looped in A. For eg in 10001, path can be A->A->A->A->B->C
Just a side note, these are not constant answers he is just giving us an idea. The NFA can look different.
I also felt the same. like for L3 = {Set of all strings that starts with '10'}. I had diff answer than him. See if we can discuss it.
yep even I felt the same, in the 1st example where we have to construct an NFA that accepts string that end with 1, in the final state probably we could just give a self loop(i.e on accepting 1 the state b stays in the final state) I guess even that's right.
@@sriinithareddy3674 no that isn't correct. We want the strings that end in 1.
thanks mann
thanx man, that's reassuring. I was kinda worried why im getting wrong answers tho.
why can't we restrict the self loop on A to only 1 instead of 0,1? Because if one 0 is encountered then it will jump to the final state and that should work fine .
Correct.
Because he wants an NFA. Yes, he could but the matter is about NFA and if he did do it would be a DFA in some cases.
@mansharkpig The point of the machine is to detect the occurrence of the zero and not it's position right?
I think the instructor has drawn the diagram just to reinforce the concept of an NFA. A simple DFA would work fine as well.
@mansharkpig incorrect , it will work fine also for the string you mentioned :)
@mansharkpig Makes sense
If this video were 0 dislikes,surely you are the no 1 educational youtuber. Helped me lot.No words to describe your efforts.Do more videos bro...
DFAs :
a) L1 = = Minimum 2 states ( All strings that end with '1' )
b) L2 = Minimum 2 states ( All strings that contain '0' )
c) L3 = Minimum 3 states, 1 dead state ( All strings that start with '10' )
d) L4 = Minimum 3 states ( All strings that contain '01' )
e) L5 = Minimum 3 states ( All strings that end with '11' )
I checked all possible strings and All are accepted. And all invalid strings are not accepted.
why l3 have mininum 3 state n 1 dead state. why l3 n l5 cant have it to? what the diff?
@@ranggagumilang7890l3 have dead state because if we get 0 I/p at starting where it will go and l5 doesn't have it because it has loop to keep it in self
remember, every DFA is a NFA, but not every NFA is a DFA
true
@@GoogleAccount-kj7bq NICE ONE
Ha..for those ending with 11, 01 I think dfa is not possible
Not true
@@AhnosIs true
great videos very easy to understand each topic is covered in depth...keep going
a)2 states
b)2
c)4
d)3
e)3
How?
@@Farahat1234 you need dead state or trap state in dfa
@@MyAsdfqwe yeah but now my paper is done😭
@@Farahat1234 hahahaa
@@abhinavs03 ky h
Thank you sir...for all the lessons...
Answer of the assignment-
L1) 3
L2) 2
L3) 4
L4) 3
L5) 4
its one of the best toc playlist and that to in english on youtube
Eg:5) Can have only 2 state namely A,B
....Make B as final sate and self loop 1 for state B
My answers for DFA are
L1:2
L2:2
L3:4
L4:3
L5:3
In EX 2) why is there a 0 from state A to state A?
It should not have a 0 from state A to state A since on a string containing 0 it should go to the final state B?
yes , don't know why he included it .. it would have worked without that extra 0 in state A
no one teach better than you really thank of you
Hello, in example 2 can we remove input 0 for self loop to first state A and only keep input 1 because it says that the strings should contain zero. So if we get zero input even once we can transition to final state?
i think we can it will run successfully
Nope, he has already clarified what you are asking here. Listen again.
Nope, he has already clarified what you are asking here. Listen again.
As far as the question is concerned i guess u r right and what he did is the case when the string is having more than one zeros. But also it is not told in the question if the string could contain one or more than one zeros, so his case also pretty well satisfies the condition.
Considering the requirements of the language , His Automata is inefficient considering time, it may take too long before we know if the language is accepted by the AUTOMATA
Assignment:-
Ex 1:- 2 states
Ex 2:- 2 states
Ex 3:- 4 states
Ex 4:- 3 states
Ex 5:- 3 states
In example 5, there should be a loop back to C when input is 1
In example 2 on giving input 0 on state A there should be only one transiotion from A to B only ,as after getting 0 as input we go on final state only.
I think for L2, redirecting the state to A on zero is redundant, since if the number starts with zero and has any thing after that it will eventually end up in state B, kindly correct me if I am wrong though
Same question, but ig its NFA so it doesnt matter.
Wow, your analysis is spot on, I didn't notice it before reading your comment.
No. of states in DFA of each of the 5 examples -
1- 2
2- 2
3- 4
4- 3
5- 4
You saved my life from the tomorrow test Tysm
consider this example 10001 for ex4 from state B it will go to FI or null state
Yeah that what i see...what if state B give zero where it will go so..self loop need to satisfy the condition i guess.. correct me if i am wrong!
In the 2nd and 4th example, I feel that the self-pointing link of A (A -> A) should be only for the input '1'. Why is it for input {0, 1}?
No we cant do like that, try 1001011 for eg 4. even though the string contains 01 it will not accepts and goes to dead configuration. Hope this helps.
@@prajwalp8070 why tho?
trying 1001011 works fine without A pointing to itself. Because once there is a 0, it should just go to the final state B. Because it means the string contains 0, which is what we need.
@@skandermahfoudh1838 Shawn is right about eg 2 but that doesn't apply to eg4
L1-3
L2-2
L3-4
L4-3
L5-3
8:45 in dfa we add one more state is called death state or trap state.
is it always mandatory to have a dead state ?
@@Sam-he4up In DFA, it is mandatory to have a dead state.
@@mehulsingh1216 no bro it is not but what is mandatory is for all the states to know where to go with certain inputs we might not need a dead state sometimes
@@Sam-he4up No need of death/trap state in NFA. It is only needed in DFA.
@@nashimbiswakarma we are talking about dfa man
I think Neso just give construct which is prone to have branches when he construct the NFA (Which may add unnecessary confusion). I think it is better to construct the necessary step first is more easy to understand. Neso do enlighten me, thanks~
In Ex 2 the arrow from A to A with input 0 is not needed. Thanks for the video!!
That's correct but it is an nfa...so it can any possible ways... it just our wish and thinking...if want more possible way..we can add self loop anywhere..it's not an error 😁✨
@@shanmugapriyam8771 error in example 2.For 011 you can't reach final state.
L1- 2 states
L2- 2 states
L3- 4 states ( one state for dead state)
We need one extra state for dead state if condition says strings starting with “substring”.ie n+1+1(dead state) here n is length of substring, in this example it’s 10 so n is 2..
total number of states=2+1+1=4
L4- 3 states
L5- 3 states
In ex5 shouldn't there be a loop of one in the final state since there can be 111 ,11111 in the end?
ya but all the previous 1s can be contained in the 0,1 self loop of A
mohit thaker Yes i didn't account the fact he was doing it for Nfa.
3:40 in ex 2 is a DFA but we have to draw NFA?
My English is not so good but i am able to understand your lecture.....i am glad that i got 2 opportunities Automata as well as English
in example 4 when on state B if we read '0' we need to stay on state B otherwise a string like '100001' would get rejected while containing '01'
for 100001 AAAABC would work, the other fails will not matter
@@niceBroKen360 noice
No 1000 would be consumed by A and them 0->B->1->C
In the 4th one, shouldn't there also be a self-loop on state B for input 0, 1
and in the 5th one, a transition from B to A for input 0 ?
@Rishika Garg there is clearly specified that the string should contain '01' so you can not put self loop on B because there after maybe it won't contain exact '01' in it.. and in the 5th example, there is no need to have transition of 0 from B to A because it is a NFA.. in NFA u don't need to specify dead state or any other extra transition of input..
@@fenilpatel4932 input '001' is valid for the 4th one, hence there should be a loop on b
that's what i thought,
@@siddhanthallan2259 We do not need to counter every possible input, '001' will be tackled when A loops back to itself on the first '0' and then proceeds to B and C on the next '0' and '1'. In NFA we just need to make 1 such path that will surely reach final state, it can still have multiple dead paths. Hope this helped.
Right, In the 4th, I think A should have a self-loop of just 1, B should have a self-loop of 0 and all others stay the same should be a better solution
Thank you soo much. it's very clear explanation
example 4 : i think at b state it goes like this (b,1)->c and (b,0)->a try with eg 00101 with both nfa's
example 5 : also in this example at b state (b,0)->a and (b,1)->c and at c state also (c,1)->c and (c,0)-> phi try to validate this with example 01011011
correct me if i am wrong
I need n+1 states to construct DFA version of those NFA, with n is the amount of states possible in NFA ( or, amount of Q in NFA )
Are you sure that is the minimum? I don't think so.
Yes, I have got n+1 states in dfa except for question 2 . Can you please explain how did you get n+1 states in q2 for dfa ?
I solved the problems with DFA and I have exactly the same number of states as solved with NFA, except ex 3, where I had to add a trap state
Can u tell me how did u get for ex3
Yeah crt😁....I were searching for the ans all over the comment... finally seen yours😉..
also for the problem 1 when doing it with dfa there will be 4 states right (1extra dead state)?
Bhai shortcut mil gaya hai
DFA required n+2 state or NFA required n+1 states in case 3. n is the length of string
In example 5, can't there be a self arrow of value '1' from C to points itself?
It doesn't make change in final answer tho
No, in NFAs you only mention transition states and self loop at the starting or ending depending whether the asked patter is in start (then self loop at end), in the end (then self loop at the beginning), in between (then self loop at the start as well as at the end)
In example 2, if we donot include 0 in the self loop around A, will our NFA be correct?
i think it should but can u answer it now after 2 years?
by the way did YOU find the answer in span of a year WILL U REPLY AFTER A YEAR
after 5 whole years, yes i think it would still be a valid nfa when removing the 0 on the self loop on A
sir, in example 4.If we want to accept the string 001,how how the NFA will accept?Explanation:present we are at A and if 0->B,now we are at B and if we again take 0 then where we will go???..if nothing is there we assume it to dead configuration ,right?..so how the 001 is accepted??
See ,in nfa u have to see all the possible outcomes of a string being given as an input and if atleast 1 of them leads to final state ,then the string is accepted.
So for string 001 ::::
A -> B -> C ,this way gets us to final state hence it is accepted
@@vipulsharma4702 where it goes after getting input o at b. it cant go to c right?
ya bro same doubt
@@Eswarsai245 no ,if 0 is given as input on b it can't go to c..
But in 001, the first 0 can change the state from A to A due to the self loop,.. ,second 0 :A to B.., then 1:B to C.... this is 1 of the possible configurations and it gets us to final state. Thus it is accepted even if the other paths cannot make us reach the final state.
Hope it helps.:)
For l1 total 4 states a ,ab,ac and abc
according to me in example 2 there is no need of giving input 0 for self loop to first state A and only keep input 1 because it says that the strings should contain zero. So if we get zero input even once we can do the transition to final state . e.g. if i get 11101 here as soon as i got 0 , the string can now be accepted , i understand there can be more than one next step for each state , but that next step should make sense. if on getting first 0 , i keep it in state A only , then on taking the self loop it stays in state A only and would not be accepted .
You give your explanation correct if it was DFA but it is NFA it will correct it doesn't a problem sister😊
@@friendsitcom2312 what do you mean? that in in self loop at state A can we only mention 1 , to make it a legal NFA?
@@friendsitcom2312 to my eyes, it is already a NFA without the self loop on A .
I think we don't need that self loop to make it NFA. As it is not defined where the State transitions on getting input one.
in example 4, b should have self loop of 0, as it will not affect the sequence '01'
Incorrect. You are giving an example of 010, but you are not accounting for ALL possible 01 combinations. You need the loop to illustrate that there are an infinite number of solutions as long as the sequence of 01... is continued.
@@tygonmaster it is confusing
@@tygonmaster what if B gets input 0
VERY INFORMATIVE SESSION, WORTH LISTENING TO IT!
Can’t we add a self loop for C of input 1,??at L5
You can, I think. But it will be unnecessary, because it is a NFA.
Wouldn't the first example (set of string ends in 1) be wrong? As I understand, NFA can move both ways so a "010" string would move to the final state when it get to "1". Is it because the final can be considered a dead state (ie. in the case of "010", when the NFA reach the last "0" the NFA would reject the input)?
When you take the example 010, so the machine is made to reject this string cause it doesn't ends with 1..... The example is correct maybe you need to watch that part again...
This 010 string will move like this......
A --0-> A --1-> A --0->A
Now Ais not final state... So, this string will get reject
assignment L1=4;L2=2;L3=5;L4=4;L5=5
You are good Neso
total state corrosponding to the sequence of questions are 2,2,4,3,2 respectively
DFA :
min no of states needed =>
L1 - 2
L2 - 2
L3 - 4(consists of dead state)
L4 - 3
L5 - 3
Do not hesitate to correct me if I am wrong 🎈
@Aryan Yadav Can't you send it back to initial state instead of a trap state?
Example 5, I think there'll be one more transition from State B to State A, because consider 1011 as a string, it wont get accepted as it would end up on the 'phi' state
can we make an initial state as a final state as well? Example #2
initial state can be made into final state... Anyways not of much use after 3 years I guess
@@neiljohn2637 Your comment helped me, so definitely of use loool
Tq for all u r lectures it really helped me a lot
Assignment Answer
L1, L2, L4 & L5 have same states as NFA except L3 - 4 states
Btw you are a great teacher
Please write your name if you see this comment
Thank you 😊
1) 2
2) 2
3) 4
4) 3
5) 3
Pls, Sir do reply if the answers are correct.
yes as same as my answers are also🙂👍
How????
1) 3
@@surendarraj715 ky
Same as mine.
In question 2, I think we can also design a NFA with no self loop on state A for symbol 0.
can anyone help me resolve this doubt , in example 1 , should there be a input 1 on state B which stays in itself ?
If you design instead of a NFA a DFA, is it a complete answer?
are they unique solutions or could there be other solutions as well? because in some examples i have some differences and they seem to work as well
No, there are many possible solutions
For example 1 we could have also written as A is final and start state with a loop of 1 on A
For the ex 5 we can also 1 input can loop to c again
A question. In L5, we can also draw an arrow from C to C with the value 1 right? It would still be correct.
you can ..but it is of no use..
as you can get all combinations of required strings without using self loop in C.
In example first considering string 1101, why transition doesn't go to state B when input is 1 and to dead configuration.How compiler know about which state to go when input is 1 since when there is input 1 in state A ,transition can go either state A or B.If it goes to state B how such strings are accepted?? Please answer it.
in the first example, instead of writing 0, 1 on A's self loop can we also draw a self loop on B for an input 1
In example 4, can we have a self loop on B with value '0'?
i think no need as you need not worry as 01 must be together all before strings can be traversed using the self loop in state A
@@pranjalsinghkatiyar4972 ok thanks :)
In the second example if A will have self loop of only 1 and not 0,1 then also it would work right?
For my case:
ans for assignment may be like
L1 = 2
L2 = 2
L3 = 4
L4 = 3
L5 = 3
A)2
B)2
C)4
D)3
E)3
why 4 for l3??
it can be 3 also..
l3...
yeah for state 3 it should be 3
how will the machine decide if by getting 1st 0 it should remain on a or move to b . as by opting the latter if it again encounters 0 it will go to dead or fi state
In L5 can we have the self loop as1 at B
धन्यवाद सर जी 🙏
3,3,4,4,4 (minimum no of states)
I think ex5 State B should have a link 0 go back to A. Or when you input 0 in State B, things become irreparable but actually it can be.
Was just looking for a commend mentioning this. Ex4 also seems to have the same issue, if B gets 0 is should stay at current state
that would be the case if it was a DFA
Very good video, sometimes the professor go through things too quick, this video helped me a lot, I could pause and have time to understand the material
Sir in question 5 it can be 011111 also as it also ends with 11
Yes, and it will be accepted by the given NFA, as you will loop at A four times before it goes on to B and the final stage C.
Thank you! Very clear explanation
1) 2 States
2) 2 States
3) 4 States
4) 3 States
5) 3 States
this is the correct one I believe:)
3) is only 3 states
@@AmineZyad i think 3 states because in case if we get 0 in example#1 so it will go to dead or trap state so if we count all states so,it will be 3 states.
@@AmineZyad why 3 state in dfa we have to make dead state also and this are ans. of dfa's
Thanx... 3 is 3, but I could get them right
In eg:3, what will happen when i give a string that starts with 0
i think the example 3 is DFA unless we put 0,1 in state A it will loop and cannot end with 10
In example 4 state B, what if we get input 0 where it should go and string not accept like 0001
look at another branch
In example 4, shouldnot there be a self loop for 0 around B?
Can there be a DFA and an NFA solution to the same problem?
A Teacher....🖤Neso🖤😉
In L4 how will 001, 1001, 10001 or 000000001 be acceptable?
State ‘B’ needs to have a self loop for ‘0’.
Exactly My Thoughts!
You are right!😑😐😐
0 of 001 will be accepted at A
The answer for assignment is:
L1= 3 states
L2= 2 states
L3= 4 states
L4= 3 states
L5= 4 states
Sir, Please do Confirm :-)
You can do the L1 with 2 states and L5 with 3 states.
In example 4, should it not a self loop on B on getting input 0?
no need because there will be a path where 0's will get looped in A. For eg for 10001, path can be A->A->A->A->B->C
How can machine decide which state to go if there are more than 1 possibility on getting input??Like in L5 if it gets input 1 either it goes to A itself or B as well.For input 11, If it goes to A on getting input-1 and again goes to A on getting input-1,It will never reach final state and it becomes wrong NFA. Can anyone clarifies this...
Pause the video and try to solve the questions on your own and then compare them with his solutions!