Converting an e-NFA straight to a DFA

  Рет қаралды 36,377

EducationAboutStuff

EducationAboutStuff

Күн бұрын

I was shocked to find very little about this technique online, so hopefully it comes in handy for some people.
At the end of the video I found a couple of errors in my answers that I corrected (though I may be wrong about my corrections), so feel free to let me know in the comments if you think something is up.
Don't forget to like and subscribe!

Пікірлер: 21
@bilawals22
@bilawals22 8 жыл бұрын
just a reminder, {1,3} should also be a final state
@educationaboutstuff3088
@educationaboutstuff3088 8 жыл бұрын
+Bill S Truuuuuuuuuuuuuuuuuue thanks I'll put in an annotation
@frankwang8611
@frankwang8611 6 жыл бұрын
Great video!!! Really helps a ton!!!!
@KieranRamnarine086
@KieranRamnarine086 8 жыл бұрын
You said union is AND, its actually OR. Just for clarification
@educationaboutstuff3088
@educationaboutstuff3088 8 жыл бұрын
+Kieran Ramnarine I'll add an annotation
@biancamarculescu1289
@biancamarculescu1289 7 жыл бұрын
why does state {2,3} with a go go {1,2,3} and not {2,3}? i mean, from state 2 with a you can go to state 3 but the e-closure of 3 doesn't go to {1,3} but only to 3, right?
@Artafact367
@Artafact367 4 жыл бұрын
thank you you helped me a lot!!!!
@gm16180
@gm16180 6 жыл бұрын
an empty set union set 1 will be equal to set 1, so E(0 u {1}) how come to be equal to {1,3}?
@vizvizoooo
@vizvizoooo 6 жыл бұрын
When you're in state 1, you would be able to go to state 3 with reading the epsilon. so the set should be {1,3}
@vizvizoooo
@vizvizoooo 6 жыл бұрын
you always need to look for epsilon transition of the states you reach and add those states to your set as well.
@brettmccausland880
@brettmccausland880 6 жыл бұрын
The reason is we no longer have the state {1} or state {3} instead we now have one state {1,3} and if the original went to either 1 OR 3 it is going to go to this new entirely different state {1,3} that we are creating
@Aditditto
@Aditditto 4 жыл бұрын
thanks a lot
@amerragab1912
@amerragab1912 7 жыл бұрын
thank you
@blueapple3440
@blueapple3440 8 жыл бұрын
i hav studied this example in "michael sipser" book.when he created DFA at the end , he added an empty state also and made transitions to them . so this thing is making me confuse .can u explain that empty state thing?
@barcode628
@barcode628 7 жыл бұрын
The automaton in the video is not actually a dfa, seeing as there is no transition for b from state 3. There has to be an empty state there for it to truly be a dfa...
@khannreactions3311
@khannreactions3311 3 жыл бұрын
@blue apple can you tell the name of book by Michael sipser ??
@wisam105
@wisam105 8 жыл бұрын
state 3 doesnt have an outward arrow for b transition!!
@SambitJena28
@SambitJena28 7 жыл бұрын
you can make a dead state for the b transition from 3 and you can loop for the dead state.
@vicvic553
@vicvic553 4 жыл бұрын
I think that you should add a dead state, and try to avoid saying "oops". It's extremly irritating. ;)
@AnkitBindal97
@AnkitBindal97 8 жыл бұрын
Please try to speak and write a bit faster. It was way too slow for such a simple example.
@phoenixultimate8253
@phoenixultimate8253 6 жыл бұрын
x1.25
Learn Regex (Regular Expressions) In Under 12 Minutes
11:44
EducationAboutStuff
Рет қаралды 11 М.
拉了好大一坨#斗罗大陆#唐三小舞#小丑
00:11
超凡蜘蛛
Рет қаралды 16 МЛН
هذه الحلوى قد تقتلني 😱🍬
00:22
Cool Tool SHORTS Arabic
Рет қаралды 94 МЛН
Touching Act of Kindness Brings Hope to the Homeless #shorts
00:18
Fabiosa Best Lifehacks
Рет қаралды 18 МЛН
Conversion of Epsilon NFA to NFA
9:41
Neso Academy
Рет қаралды 1 МЛН
Conversion of NFA to DFA (Powerset/Subset Construction Example)
12:31
E-Closure : E-NFA to DFA Conversion
12:51
Mifta Sintaha
Рет қаралды 201 М.
Conversion of NFA to DFA Examples (Powerset Construction)
14:26
Easy Theory
Рет қаралды 9 М.
P vs. NP and the Computational Complexity Zoo
10:44
hackerdashery
Рет қаралды 3,4 МЛН
How to Convert NFA to DFA: Dealing with Epsilon Transitions
13:45
Mohammad T. Irfan
Рет қаралды 30 М.
Context-Free Grammar to Pushdown Automaton (and Equivalence)
7:03
EducationAboutStuff
Рет қаралды 44 М.
Conversion from NFA with ε to DFA | Automata Tutorial
12:33
CSE & IT Tutorials 4u
Рет қаралды 7 М.
TOC Lec 10 - Epsilon NFA to DFA by Deeba Kannan
18:06
DEEBA KANNAN
Рет қаралды 232 М.
拉了好大一坨#斗罗大陆#唐三小舞#小丑
00:11
超凡蜘蛛
Рет қаралды 16 МЛН