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.
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
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
I think we don't have a complete proof of correctness of the automaton for the "contain 0101" language (3rd problem). You kind of described each step of development of your automaton, but I think it still doesn't fully prove that it will return the correct result for a word that does/does not belong to the language. Correct me if I'm wrong though
For {w | w is any string except 11 and 111} there is even a simpler way to look at it. Consider 111 as redundant because 11 is its substring and there is no size limitation. In other words the language {w | w is any string except 11 and 111} is equal to {w | w is any string except 11} Correct me if I am wrong.
This is incorrect. The language {w | w is any string except 11} can be represented by taking the DFA in the example in the video, and simply removing the 4th state from the left. Then letting the 3rd state from the left transition to the final state on both 1 and 0. In general, 2 languages are equivalent if and only if they are the exact same set of strings - so L1 = {w | w is any string except 11 and 111} is not equal to L2 = {w | w is any string except 11}, because 111 is an element of L2 and not an element of L1. Were you considering that maybe the DFA could be simplified by building in a loop to a trap state, and letting that loop represent 11 and 111? This would be a good idea if the language was something like {w | w is any string except 11, 111, 1111, or any string greater than length 2 consisting of only 1's}. Then you could use the argument that 11 is a substring of 111, and 111 is a substring of 1111, and simplify it that way. But the example in the video is too specific and needs to be handled the way that was shown.
@@ryanconnolly-kelley1807 Basically for some weird reason I got confused and thought that the language was what you mentioned in your reply. "{w | w is any string except 11 or any string greater than length 2 consisting of only 1's}."
12 days ago you posted this. 12 hours from now you will have saved my final exam. thank you.
Well??
No longer taking this class but thanks for the help when I took it! Your videos were really helpful.
i’ve been out of this for 2 years now i used to love these so i’ll watch anyways
got more information from this video than 4 lectures, thank you
damn! professor is back!!
Love your videos, they are the only reason I am not completely lost in my Automata Languages class
you sir are a person on par with Sipser himself, thank you so much ❤❤❤❤❤❤
Наконец-то я начал что-то понимать в этом DFA. Спасибо!
I think I’m going to use all of your videos to study for my cs theory final. Tysm for these
Very Helpful Bud, Thanks a lot
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
No Patreon, but thank you!
The GOAT
Love the upgraded production quality !
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.
Thanks sir, but it would be even better if regular expression for each
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
I wish my school had more TOC classes miss this lol still fun to practice though lol
Sir can you make a playlist for Compiler design tutorials please? Your automata lectures are awesome by the way. Thank you
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
36:55 could we just choose one condition and ignore the other?
Thank you sir
I think we don't have a complete proof of correctness of the automaton for the "contain 0101" language (3rd problem). You kind of described each step of development of your automaton, but I think it still doesn't fully prove that it will return the correct result for a word that does/does not belong to the language. Correct me if I'm wrong though
34:28 which transition is redundant and why?
The state is the right has a recursive transistion 1,0 and 0 . Die zero transistion is redundant because is a subset of the 1,0 transition
y 14 ? y not 15 :/
For {w | w is any string except 11 and 111} there is even a simpler way to look at it.
Consider 111 as redundant because 11 is its substring and there is no size limitation.
In other words the language {w | w is any string except 11 and 111} is equal to {w | w is any string except 11}
Correct me if I am wrong.
This is incorrect. The language {w | w is any string except 11} can be represented by taking the DFA in the example in the video, and simply removing the 4th state from the left. Then letting the 3rd state from the left transition to the final state on both 1 and 0.
In general, 2 languages are equivalent if and only if they are the exact same set of strings - so L1 = {w | w is any string except 11 and 111} is not equal to L2 = {w | w is any string except 11}, because 111 is an element of L2 and not an element of L1.
Were you considering that maybe the DFA could be simplified by building in a loop to a trap state, and letting that loop represent 11 and 111? This would be a good idea if the language was something like {w | w is any string except 11, 111, 1111, or any string greater than length 2 consisting of only 1's}. Then you could use the argument that 11 is a substring of 111, and 111 is a substring of 1111, and simplify it that way. But the example in the video is too specific and needs to be handled the way that was shown.
@@ryanconnolly-kelley1807 Basically for some weird reason I got confused and thought that the language was what you mentioned in your reply.
"{w | w is any string except 11 or any string greater than length 2 consisting of only 1's}."