Easy Theory

Easy Theory

39,800 subscribers

⏱ 👁 55,171 views

Fourteen DFA Examples? No Problem!

Video Overview & Insights

Here we solve Sipser problem 1.6, which involves 14 DFA (Deterministic Finite Automaton) problems. I give my strategies as well as ways for solving other problems.

“

Sir do you reply to questions, could you please explain when I have to put a self loop and when I have to draw a directed arrow to a state? Sometimes I draw the arrow to the previous state when I'm supposed to draw a self loop. Thank you sir for your help.

— @considerthelilies48

Easy Theory Website: https://www.easytheory.org

GoFundMe: https://www.gofundme.com/f/easy-theory-video-studio

“

Thank you so much. Thought I was stupid and didn't get it but it turns out I just needed examples with incremental complexity instead and it makes sense! Thank you so much for this video!

— @redelman43199

Patreon: https://www.patreon.com/EasyTheoryYT

Fourthwall: https://easy-theory-llc-shop.fourthwall.com

“

I am currently in CSCI 4890 at LSUA, and one of the review questions in chapter 1 is 1.4a-1.4f which gives these simple union expressions and asks for a DFA. By the end of it I was able to do it with your help, albeit needing some simplification and removal of unnecessary or repetitive states. Thank you from 2 years later.

— @frankybodanky

Problem Solving channel: ⁠ @easytheoryprobsolve

Timestamps:

“

thank u :D

— @StudyMan-e1n

0:00 - Intro

0:19 - DFA for binary strings beginning with 1, end with 0

“

Helped a lot just 1.5 hrs before my exam

— @AnirbanBiswas123

3:02 - DFA for binary strings with at least three 1s

4:50 - DFA for binary strings that contain 0101

“

For #15 the wording had me confused, reading 110 not a substring in my mind was to accept 110, but just not in a substring

— @ArnavS21

8:39 - DFA for binary strings with third symbol 0

11:01 - DFA for binary strings that start with 0 and odd length, or start with 1 and even length

“

Your videos have been a lifesaver for my discrete structure 2 class. Thank you so much.

— @andy.mp4507

14:59 - DFA for binary strings that do not contain 110

18:57 - DFA for binary strings of length at most 5

“

When do you use union product construction vs intersection?

— @donk1647

20:51 - DFA for binary strings that are not 11 or 111

23:42 - DFA for binary strings with every odd position 1

“

@EasyTheory 29:13 How come we dont make any pair that had a final state in it final since we are using product construction and union like your other video?

— @NoahTorres-x4p

26:28 - DFA for binary strings with at least two 0s, and at most one 1

31:29 - DFA for binary strings that are either empty or 0

“

Thank you for making these! There are so many other videos with thick accents that bug me, but you speak very clearly! Im studying for an exam i have in like 2 days

— @Mirit0ModMadness

33:00 - DFA for binary strings with even 0s or exactly two 1s

37:07 - DFAs for emptyset, and all nonempty strings

“

Thanks a bunch big bro

— @arsh2795

All of the transition videos are from StefWithAnF: https://www.pexels.com/@stefwithanf-1955763/.

If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1

“

at 26.24 should the DFA in the second state not only have one transition value like 0. The language is {w ¦ every odd position of w is a 1} and our first state passes a 1 to the second state (a final state) and the the second state (final state as well) passes a 0 and a 1 back to the first state. This would mean 11 could be an accepted string??

— @darraghkerins1543

More User Perspectives

@

14:45 I have a minimum solution :

q0 -> q1(A) : 0

q0 -> q2 : 1

q1(A) -> q2 : 0,1

q2 -> q3(A) : 0,1

q3(A)-> q2 : 0,1

@casual_nomad_xyz

@

legend of the history

@Nacho13413

@

26:18 how is that possible if we say the start state also a final state are we accepted the "empty" situation ?

@bugra1990

@

Love you my nigga

@exile9645

@

23:38 can be minimized in the following way:

From q0: Reading '0' stays in q0; reading '1' goes to q1.

From q1: Reading '0' goes back to q0; reading '1' goes to q2 (non-accepting).

From q2: Reading '0' returns to q0; reading '1' goes to q3 (dead state).

From q3: All inputs stay in q3; any further input remains rejected.

Only states q0 and q1 are accepting, rest rejected.

@UdbhavAshish-g3k

@

thanks, so useful, starting my third year in few days...

@YazeedSeraj

@

I am a little confused about the DFA for binary strings with even 0s. Please, someone, help me!

@yofionayang

@

14 NFA examples pls

@SKY_LUNAR_WORLD_winterghost

@

thank you bay harbor butcher

@WencyCasiño

@

Thank you sir this really helped me through my discrete structure course 🤍

@adwemad

@

you teach so well , thanks professor !!

@amanrajpoot8164

@

one of the best video on dfa ever watched in yt

@ABHISEK_GHOSH

@

36:57 , If I am not wrong, isn't the DFA accepts more than 2 1's??? because if the string w=111 then it will go to an accepting state on the top right state.

@kaifahmedkhan

@

this is spectacular, give me fourteen of them right now

@siratrocidad

@

Thanks a lot for this amazing practice. From india 🎉

@neyahnk8687

@

thanksssss

@leafar7674

@

for the fifth problem, I think we can merge the lower half with the upper final state, since that would still hold the properties and reduce the DFA by one state

@gimme_a_good_name_bruh

@

you look like you are about to shit the information deep into my soul

@carmony8756

@

you, sir, are a legend. thank you so much!!

@empowercode

@

Very helpful, really appreciate you!!!

@rasel_hossen_0

@

Very helpful, really appreciate you!!!

@SaeedSekandari

@

Thank you so much!!!!! 🙏🙏

@lalalanding234

@

God bless you

@Karen-gu2dz

@

8:08 i dont see any problem if we stay in initial state than traversing back to second ? , both the traversals still yield out "0101" eventually no?

@varun_mhatre

@

Had too much fun doing these problems!

@TusharDeb

@

Thanks for the questions and your wonderful explanation sir !!

@vsk0705

@

Love from holland <3

@nielsdejong2322

@

Didn’t quite understand the penultimate one. You could use the string “1” and it would accept it because there was an accepting state there. Can somebody please explain it to me?

@arianqamili3642

@

Very Helpful Bud, Thanks a lot

@hemanthkumarsharab1635

@

36:55 could we just choose one condition and ignore the other?

@GordonGoodwell

@

you sir are a person on par with Sipser himself, thank you so much ❤❤❤❤❤❤

@rajveerajmani

@

26:14 is this statement correct? What does it mean for the starting state to be accepting? Does that mean the DFA accepts the empty word as well? I was more thinking in lines of:
-->s--1-->e1--0-->e2 ; s--0-->dead ; e1--1-->s ; e2--1-->e1 ; e2--0-->dead
I tried to type out my diagram here, I hope it is understandable hahaha

@Patanegn

@

got more information from this video than 4 lectures, thank you

@RobertTheBrick

@

Out of curiosity, do you have any experience studying /researching/teaching Algorithmic Game theory? Its one of the few undergrad theory CS electives at my school's CS department and it seems like a somewhat uncommon but really cool subject

@aliasjon8320

@

Наконец-то я начал что-то понимать в этом DFA. Спасибо!

@anonymous8324

@

Sir can you make a playlist for Compiler design tutorials please? Your automata lectures are awesome by the way. Thank you

@Anupama_Ghosh

@

i think problem 5 the soultion is not minimal. we can club the two final states and the empty state that is going from o with the first transition after 1. this will still count even and odd for 1,0 respectively. so we endup with 3 states - 1 start, 1 final, 1 non accepting state that comes either after start state with 1 as input or any input after the final state.

@phani8482

@

Bro, Do you have a patreon? I would like to support you in any little way i can. The intuition i am gaining from your videos is priceless

@phani8482

#easy theory