Conversion of NFA to DFA

TOC: Conversion of Non-deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA).
Topics discussed:
1. This lecture shows how NFA and DFA are equivalent and how to convert an NFA to its equivalent DFA.
2. Equivalence of NFA and DFA.
3. Example of converting the NFA for a language that accepts all strings that starts with '0' to its equivalent DFA.
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.org/donate
Memberships: bit.ly/2U7YSPI
Books: www.nesoacademy.org/recommende...
Website ► www.nesoacademy.org/
Forum ► forum.nesoacademy.org/
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
#TheoryOfComputation #TOCByNeso #NFAtoDFA #NFA #DFA #AutomataTheory

[@andrewschatz3949]

You deserve an award. You've probably saved more lives than Superman.

[@_johnakinola]

Yes you are more than correct. After 3 weeks of classes in confusion, my questions were answered in 9 minutes

[@himanshujain718]

Please
Construct an optimized DFA :
0*1*(0/1)#

[@aananthijs294]

Exactly

[@sohammaity7389]

are you an idiot??

[@KM-sf6zy]

@@sohammaity7389 I think you're the one

[@prajunathunt]

A day before the exam at 2x speed.

[@bgregz]

Technically day of for me (:

[@erickill3r925]

3 hours before the exam

[@godzilla362]

more like 7 hours from exam.

[@alokgoldy9219]

Doing the same

[@shashankshetti4477]

During Online Exams from home :P...

[@LuisHerrera-vr5fk]

I learned more in 10 minutes than I have in 8 weeks paying $1K in class. GPA savior.

[@gena8414]

then your class is shit.

[@observantmagic4156]

You need to change ur classes bro

[@damianwysokinski3285]

Waste of money. Universities should not be paid by students.
Especially useless subjects

[@LEARN-LEGENDS]

From having no knowledge about my compiler engineering subject to kickoff the subject like a master , I've come a long way with your teaching sir .... THANK YOU SO MUCH !!!

[@tr_olia695]

I put aside my university study materials because they are useless (lack of explanation) for the sake of this course and instead of stomping around in one topic/exersize for a week, I have already gone through half the material in 3 days with examples. Thank you very much!

[@217-sritejrajulu6]

u have made the subject which i feared look damn easy, thanks a lot for your teaching, stay blessed sir

[@soumyaranjansamalkiit]

+1

[@ArBasith]

Appreciate your work, helping me a lot with automata theory. Very simple and detailed work, keep continuing it.

[@pallasepithet]

I've been reading comments under algorithm tutorial videos and I learned more ways to flatter than to program

[@forgotaboutbre]

This example is too simple as the NFA & DFA are nearly identical

[@gena8414]

yeah, the main problem is when an NFA state has multiple transitions for the same symbol/

[@kaywilfert8297]

Really helpful! Thanks a bunch. You make it practically trivial to understand

[@Drummerboy19th7]

Today I also converted to a DFA:
Definitely
Fixing-for
Academic Probation

[@arashkeyghobadi]

Thanks a lot, man! got a headache reading my lecture notes to figure it out but you put it pretty nicely!

[@jevierizzamaulana4803]

This is the best example ever. Thanks a lot sir...... Tomorrow is my test and your explaination help me a lot

[@ropopal1094]

all your videos are good, easy to understand, well edited/produced. thank you. you are a good man!

[@yasina63]

Wow, your teaching style is a piece of cake.
Thanks a bunch.

[@ProfessionalTycoons]

very clear-cut explanation

[@Travishead7812]

Wow. Brilliant 👏
Very Good tutorial in few minutes. Thanks. Cheers

[@AbhishekVerma-fe3wo]

This channel is a gem for engineering students.

[@DanesZalor]

thanks for saving my cs career

[@supersakib62]

Great videos! A correction maybe: In NFA the delta function goes from Q times sigma to P(Q). The power set. 2^|Q| is the cardinality of that set.

[@Emily-fm7pt]

Yeah, though a lot of textbooks and resources use 2^Q as the notation for the Power Set, so that's probably just what he was used to

[@zzzzzzzjsjyue2175]

You’re the one that’s wrong. That notation is also used for the power set dumbass

[@declanleighncsu]

This was incredibly easy to understand.

[@lima073]

You're able to make everything look simple

[@aniketsrivastava1870]

i just wanted to remember this from my previous sem toc subject cause this is asked in my compiler design subject and this video is real bomb.....

[@rehabpasha7322]

Really helpful! Thanks a bunch :)

[@Luna-fu7ix]

OMG.....BEST EXPLANATION EVER.........!!!!!! Sir i dont know how shoud i thank you....

[@AkhzarFarhan]

Contribute: www.nesoacademy.org/donate

[@shantakumariymr8601]

Wonderful explanation

[@chandrashekharreddy4524]

Today I wrote my exam and I'm going to pass just because of you...🧡

[@karanveersingh5535]

sirf pass , atleast 2nd toh aa jate.

[@praveenp1369]

U Correct the paper then he will get 😂

[@joshuapaul652]

Your explanation is very nice

[@dishaenglishmediumschoolkantab]

Very Very Amazing Class For Me.... Thanks Alots Sir🙏❤️

[@uttukoul]

literally reading this 3 hours before my end sem exam.

[@learn_tube01]

Best explanation. Go ahead!😍🥰

[@phumlanimbabela-thesocialc3285]

Thank you very much. Great video.

[@EchoVids2u]

Thank you so much!

[@vivienne_lavida]

Why are there so many dislikes? I think this is an accurate video of NFA to DFA conversion.

[@Jaqen_Hghar]

Because some people always dislikes no matter how good the video is....

[@kanav51]

Because you cannot be successful if you don't have haters.

[@mouradqqch1767]

Because it is simply wrong. The example shows how to convert an incomplete DFA to a complete DFA. There is no nondeterminism in his automaton.

[@patrickmutuku]

@@mouradqqch1767 Yes. Exactly the point.

[@arunyadav4439]

👌👌👌🙏

[@Topa43211]

Nice explanation of concept

[@chavaligangadevi8663]

good explanation sir

[@eimaldorani]

@Final state, in the bases of what did you decide that AB is the final state!?

[@skeitra6536]

so basically, when it comes to NFAs that have only one next state for each symbol like the one in the video, it's equivalent DFA needs a specified transition for every alphabet symbol, can't just make it go nowhere (empty set)?

[@anshikagupta2213]

Assignment ans: L2 -2 , L3 - 5 , L4 - 3 ,L5 - 5

[@msdhoni761]

Thankyou very much. It is very useful.

[@booleandilemma]

this is great, thanks bro

[@rimshasarwar9592]

thank you do much neso acadmy

[@nitishrao2561]

Please make tutorials on compiler design.

[@GeneralMonday]

thank you so much!

[@deekshith9028]

Thanks for helping me before exams

[@primakovch8332]

can we take both 0 and 1 and go to the same state in case of DFA??

[@kirantejaa74]

thanks sir!

[@elizabethgrant6018]

Thank you A LOT

[@user-bv3no6tj8u]

tjanks bro this so helpfull

[@Bellemere...]

Thank you so much Sir!

[@ariap9697]

Nesco is the best Tutorial Online Education (Thanks for being free I really cant afford even for Univercity easily)

[@Anwari70]

well explained

[@xxsun2013]

I am not quite sure if this it correct when you say DFA has Q state and NFA has 2^Q. Because in the book intro to automata and computation page 61. It says the opposite.... can someone answer my question? Thanks!

[@ProfessionalTycoons]

Amazing video, thank you!

[@diogo98s]

Boa sorte para TCOM pessoal!

[@8089525315]

Thanks

[@NishuTissue]

What do you do if the same input is going to 2 different places. In one of my examples the 1 is going to A and B.

[@vishalprasadgupta714]

you are great sir

[@balanusa1523]

THANKS!!!!

[@keitogoto6629]

まじありがとフロムジャパン

[@krithikaravichandran5706]

Awesome!

[@stevenlee3905]

thank you

[@USITACADEMY]

thank you soo much dear .....respect and love for you

[@NoName-jy4cv]

Thank you!

[@rohitippili3834]

Thanks 🙏🏼

[@indhumathi4783]

Thank you sir❤️

[@meetbhure9977]

Thanku neso

[@guptav06]

Sir, the example you have taken is not a NFA, but that is DFA itself.

[@alihelmi]

In this video, you considered Phi as a new dead state in the NFA transition table, while in the coming videos you didn't create a dead state in the transition table of DFA! Could you please explain why?

[@imposter1721]

phi in NFA means dead configuration (basically when a state does'nt goes anywhere after input ) in DFA it is then converted to dead state to make the DFA complete.

[@ganeshkumarr3310]

sir the first example you showed for set of all strings that start with 0,why it needs a dead state?
If 1 comes to A ,can we show that it stays on A itself.

[@erickgomez7775]

If you use your suggestion the automaton will accept any string that has at least a zero. The string 10 would be accepted. Which is not part of L

[@arabindrajak4951]

how we get the final state with the help of transition diagram??
pls anyone reply

[@devi_dadisetti9366]

Wt about dfa to nfa sir??is this same for that

[@gabrielsales7402]

Why would I wanna convert? Is it because an NFA is easier to design but only a DFA can be implemented?

[@bhuppidhamii]

love the intro.

[@cosmic_voyager_]

💞 thanks for being there man. You have saved me a lot of times😅😂

[@kainaatmakhani6550]

good lecture

[@agamgill9563]

Thank u sr....

[@urizoran]

This is not the technique of how to convert a NFA to DFA, which is more complicated than this. This video shows the technique of converting a non-complete DFA to a complete DFA. I think the technique is explained well but it is misleading.

[@lowzyyy]

He basicaly did convert non complete NFA to complete NFA. Lol dislike

[@urizoran]

@@lowzyyy The "NFA" in the example has no non-determinism, which means it is basically a DFA. Since the transition function is not fully defined, it is a non-complete DFA. The generic technique of converting an actual NFA to a DFA involves simulating the many possibilities of states the automata can be in at any moment in the computation by using 2^|Q| states, each representing a set of states of the NFA.
I am sure the intentions of the uploader were good, but the content does not actually teach the technique students are usually expected to understand when learning of NFA to DFA conversion.
Hate to break it to you.

[@Golha2505]

YES, its annoying that he didnt correct the video.

[@pradhumnkanase8381]

@@Golha2505 @urizoran he has actually has more example videos you can check that out

[@faheemmahmood3475]

its NFA, you're misleading

[@pritamshil9079]

thank you sir

[@swapnil1]

every DFA is an NFA , then if we are asked to design both DFA and NFA for some language , isn't it enough to just only design the
DFA ?

[@gabrielpereiramendes3463]

Excelent!

[@devmahad]

So converting using this state transition table.

[@nomimalik7025]

my teacher is big fan of you!!!!

[@vinaylodhi6475]

Bahut badiya

[@gabethebabe3840]

good stuff

[@StreetArtist360]

thanks

[@Aba9846]

Brilliant

[@unaissid2538]

So what to do if the NFA has an empty string or lambda? For Example, a NFA is; S state goes to 1 when it gets a, then state 1 goes to state 2 when it gets b, and state 2 goes to S state when it gets a lambda/ empty string.

[@freebobbyshmurda600]

How can I replace my incompetent professors with you? Thank you so much

[@soumyaranjansamalkiit]

Kya chummeswari padha te hai sir 👌🏼

[@Leo-mq6ig]

Sir.... In NFA any state have multiple transition for any input... But in ur Example where it is... State A has only 1 transition for ip 0 and B also.
Is is NFA??

[@neiljohn2637]

5*3 done

[@dhanushsivajaya1356]

Thankyou sir

[@ashwinmryt8664]

this subject is hell it is so tough to learn uff

[@rohanthamke8777]

From where i can study computer organization and architecture??

[@ineshraina2627]

sir , but u said that DFA should be linear and every state should have 1 next state then why do we have 2 states in A when we convert NFA to DFA sir ?

[@kiranmaik7128]

Tq very much

[@riteshsharma9838]

it was just wow!😱😱😱😱😱😱😱😱

[@shantakumariymr8601]

I love❤😘 this channel

[@dovic9181]

2 hours before exam up 24 hours and with 5 cups of coffee taken