A Quick Non-Deterministic to Deterministic Finite Automata Conversion

Подписаться 28 тыс.

Просмотров 20 тыс.

50% 1

In this lesson, we convert a non-deterministic finite automata (NFA) to a deterministic one (DFA). It is assumed that the viewer is at least partially familiar with the differences between these two classifications of finite state machines.
Timestamps
00:17 | Problem definition
01:31 | RegEx to state diagram
02:38 | Diagram to transition table
04:52 | Initializing the set of states for the DFA, Q'
05:51 | Iteratively building the rows of the transition table
11:55 | Identifying accepting states
13:01 | Relabeling the states
14:32 | Creating the DFA state diagram
16:59 | Evaluating our new state machine
Hashtags
#deterministic #finite #automata

Опубликовано:

29 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 39

@IMominMahmudJalib 2 года назад

This channel is gonna blow up someday. It deserves more subscribers. Too good production quality.

@benr3346 2 года назад

aaaand a legend was born...

@adimasariefrahman8555 2 года назад

this channel should be recognize by peoples

@roccococolombo2044 5 месяцев назад

Ça ne peut être expliqué plus clairement. Bravo.

@DavidLindes 9 месяцев назад

Well, this is out of order, but having another example NFA helped me catch a bug in my code to create a DFA from one, based on the recent Computerphile video. Of course, I might also have to re-think some things, because I don't keep around the empty-set transitions (or state e, in your final form)... instead just returning False if there's not a transition defined between two states (and, for example, I don't define a transition for starting at a and getting a 1). I'm fairly certain the effect is the same, but it looks different. Interesting.

@bhspringer 2 года назад

Thank you that was amazing

@Intermation 2 года назад

You're welcome! I appreciate the kind words.

@sohailshaikh786 10 месяцев назад

Nice explanation

@sek0ner7 Год назад

Are you the god or something?

@jediboybetos5759 2 года назад

Non-deterministic finite automata also has something called epsilon transitions. Can you make a video converting NFA with ε to DFA?

@Intermation 2 года назад

That's a great idea. I was so focused on moving toward implementation in hardware (which doesn't address epsilon transitions) that I didn't think anyone would be interested.

@angz2717 8 месяцев назад

didn't know Walter White gave CS lectures

@carldea 11 дней назад

Wow. So impressed. It's time to get rid of if statements. Just discovered this channel. How the explanation fits on the screen is beyond me. Thank you sir!

@cricketmaster7697 5 месяцев назад

Hey i had a question. Sometimes this method doesnt work and we need to use an epsilon transition method instead. How do we know if an NFA can be solved in the way described in this video and when we need to use the epsilon method?

@yousefali995 2 года назад

I don't know why this channel isn't getting millions of views

@PG-jv5nw Год назад

You are truly a great educator. It takes hours and hours to understand this topic but you explained in just few minutes. Your video makes me think how much garbage is thown at us in college.

@riddle-me-ruben 8 месяцев назад

Wouldn’t “000” be rejected even though it should be accepted"? We have a 0, then any number of 1’s (in this case 0/none), and still end in a 0. But it gets rejected as it follows states a,b,c,e (rejected)

@riddle-me-ruben 8 месяцев назад

Oh I see. Concatenation says we should start with 0, have any number of 1’s, then immediately end in 0 or 1. 000 should be rejected. As it does not immediately end in 0 but there is another 0 that follows.

@relaxationwithboama Месяц назад

How's he writing like that 😢

@travisquigg2450 2 года назад

My only pet peeve is the squeaky sound of the marker. Other than that love the videos. Very informative!

@computersciencestudent1129 2 года назад

such a great example it cleared all doubts I had for converting from non-deterministic to dertinistic thank you !!!

@tiara7624 5 месяцев назад

Very nice thank you so much

@georgiaanast3462 27 дней назад

thank you!

@keegster7167 2 года назад

Thanks!! I’m studying in a graduate course for human language technology and I couldn’t quite see the picture of what was going on with this until now. Beautiful video btw

@a_wheelbarrow Год назад

What if the original NDFA has multiple exit-states (let's say they are q2 and q3; q0 is our starting state and q1 is neither). Will our DFA's exit states be the ones that have BOTH/ALL of the NDFA exit states (so {q2, q3}, {q1, q2, q3}, {q0, q2, q3} and {q0, q1, q2, q3}) or if they have ANY of the NDFA's exit states (so {q1, q2}, {q2}, {q3} etc.)?