How to Convert NFA to DFA: Dealing with Epsilon Transitions

All DFAs are NFAs, but not all NFAs are DFAs. How can we convert an arbitrary NFA to an equivalent DFA? This video shows how to deal with epsilon transitions during this conversion.

[@ODAKAB]

cleanest and the clearest explanation even covers starting with an epsilon transition

[@abenezertasissa49]

WOW! perfect! the clear and consice explanation added with the amazing visuals, audio pacing being constant + composition and your way of covering a bunch of concepts within one example is perfect! loved it! Thank you!

[@exxzxxe]

Excellent presentation.

[@Iqbal00123]

Great video brother , please keep it up

[@zaidooos]

this man is good af thanks life savor

[@junderfitting8717]

You are amazing!

[@BakuValorant]

on nfa can you say that we can include s in new input states from {a,s,f} on 1 input with epsilon, followed by 1, then same epsilon transition again?

[@abellacherabah6284]

Thank you teacher

[@samUmi]

Thank you!

[@movocode]

best explaination

[@gauravmaur9080]

thank you so much

[@emilysahyoun8376]

why isnt s part of the set for {a,s,f} on 0?

[@EzzzZZZ___]

Amazing video, jazakAllah Khair for clarifying epsilon transition

[@sanoucedric6471]

very nice! thx

[@ngocchaunguyen8685]

Appreciate your clear explanation. Please continue making Computer Theory videos, such as converting regular expression to NFA and vice versa. Also, didn't mean to point this out, but because we are building DFA at the end, shouldn't our DFA have trap states? Anyway, thank you for your video, sir.

[@kyrrodi9498]

State (g,f) can be omitted, and the 0,1 transition can be from (a,s,f) to itself. I'm not sure how you got the state (g,f) in the first place, given there are no forward epsilon-transitions (indeed, no forward transitions at all) from state (g) or state (f) in the NFA.
Essentially, if a newly created DFA state is a subset of any of the others, it doesn't need to be included.

[@irfan_]

RE: "not sure how you got the state (g,f) in the first place." First, make sure you understand how we got the state {a,s,f} in the first row of the table. Now, consider 0 transition out of {a, s, f} (third row of the table). Observe that we can go from a to f on a 0 transition in the NFA. We can go from s to g on a 0 transition. Hence, we obtain {g, f} from {a, s, f} on a 0 transition. Makes sense? The video has a detailed explanation, including 0 transitions.
Furthermore, your comment on subset is not true in general (and needs to be further refined). In particular, there are worst case examples (see the "Dragon book" of compiler design) showing that n number of NFA states may lead to 2^n DFA states, where you MUST retain all the subsets.

[@stephenjamesconnelly7564]

great !

[@misspps_]

thankss

[@victorliu9629]

shouldn't DFA cover all of the transitions(0 and 1)? g and g,f doesn't have any transitions

[@irfan_]

This is because in the NFA, there is no transition out of g or out of f. In general, we cannot have a transition in the DFA that does not exist in the NFA.

[@kodtld]

Thanks for the very helpful explanation!

[@sun-eq8yw]

Awesome!
please, what is the app you use?

[@sebastianklin]

Goodnotes

[@sun-eq8yw]

Please more video on computation theory, and all amaizing stuff . All the best !

[@sarvsarv6349]

thank you a lot.. also i think we must create a dead state to have complete dfa.

[@ryoony1993]

I agree

[@lockness_gaming7634]

What happens when f epsilon to another state

[@farazahmad8118]

can you refer a book?

[@irfan_]

This is based on Michael Scott's Programming Languages book.

[@MuhammedCheema-sl3lp]

should {g,f} not be {g,f,s} because u can go from a to s through epsilon.