Thanks to my supporters Yuri, vinetor, Ali (UA-cam) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.
Dude... I love you. The in and out list made this so easy. My college professor was just having us send it and I couldn't get it, you legitimately just saved me for my mid term. I wish you were my professor, thank you!
Thank you soooo so much!! I didn't understand what my professor was doing in the lecture because he didn't explain what he did and why he did it. You saved me !
Incredible. You are a great professor. I like it when you put it into steps. It is really easy theory. I think the biggest challenge is just explaining it and you do a very good job at it.
Thank you so much! I have review the lecture and read the book more than 2 hours in order to undertand the GNFA, but I failed. I have watched this video about 7 mins, I figured it out.
How do you know when to combine different paths from a state to another state with a union? There were times where there were alternative paths from one state to another but they weren't included in the union. For example at 6:03, to go from q2 to F we could've taken the that q2 -> q0 -> q1 -> q3 -> F but we only chose the path shown in the video. I'm not sure if this is just intuition or there is some algorithmic and definitive way of doing this. At 7:15 you did a union here but I'm not sure why union wasn't done in the other case I mentioned? In other words how do you know which paths to choose to get from one state to another? There are some other paths you could've taken from one state to another but chose not to.
Question: Is Union equivalent to "+". In my classes we use the + sign and not the U. If they are can i directly substitute to get the desired answer from my Uni?
Hello this is a great technique! I had a doubt though. What to do in case we have a trap state? How to "rip" that state out? I don't see how to do this since trap state never comes in the path to final state. My gut is telling me to just ignore the path to trap state but I'm not sure if that's right. Edit: I figured it out! Since this method is agnostic to whether this is a DFA or NFA, we can just ignore the trap states before hand!
Note that there would be no outgoing transition in that case. So the number of new transitions is 0 when you rip it! :) (There is a more formal proof of that but that's the basic idea)
Thanks for the nice explanation. Why do you ignore the transition from q1 -> q2 -> q3 -> F when you're ripping q3? I think it doesn't make a difference but I just wonder because later you consider "longer" paths.
Because of transitivity. If we know how to get from q2 to f, then we know how to get from q1 to f because that's just concatenating the two regexes along the way.
Thank you very much for your clear explanation. I have a question though. You mentioned that you can pick any state to get started. However, elimination states in different order will likely produce a different RE. E.g. if I eliminate states in this order: q2, q1, q3, q0, I will get the result as (a(bUaa))*(a(abUe)a*), where e is epsilon. Is there a way to convert that RE to a((bUaa)a)*(a*Uaba*) which is what you get? or prove those two are basically same?
Great video, thanks! One question: How do I build pairs in the In-&-Out-list if there is a state with several Ins and several Outs? Do I have to treat this a cartesian product so that every In builds a pair with every Out?
It's not exactly the Cartesian product, but some kind of product, yes (it's possible to formulate it as Cartesian though - the problem lies with the results being concatenations, not ordered tuples as the Cartesian product would give.) But yes, every "in" goes with an "out".
Thanks to my supporters Yuri, vinetor, Ali (UA-cam) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.
College professor spent 2 hours explaining this. Watched this video on double speed in 7 minutes.
Lmao good!
Your tuition money at work
agree
Wish textbooks had more examples because they help a lot more compared to just text and theorems. Thanks so much!
I'm writing a textbook! See my latest video.
I have a test tomorrow and didn't understand anything from my Lecturer . This video is a gold mine. Thank you!!!
You're very welcome!
Same, 3y later
Thank you so much for this easy to follow explanation! Was so confused by my professor but you're a life saver
You're very welcome!
Didn't understand anything from my professor's book, watched this and understood everything thanks !
Dude... I love you. The in and out list made this so easy. My college professor was just having us send it and I couldn't get it, you legitimately just saved me for my mid term. I wish you were my professor, thank you!
I have an exam tomorrow and this just saved my life. Thank you for making my Computer Science life a bit easier.
Good luck on your exam, and thanks!
This is a fantastic explanation. The In/Out decomposition really helped!
You're welcome!
Thank u sir from INDIA, there r very few utubers who have covered this topic but from all those, ur explanation is outstanding.
searched entire youtube for such an example, thankyou so much 👍😁
hands down the best tutorial on FA to RE conversion using GNFAs
Hats off, tried 10+ resource and now this is the only video i will refer in future as well for NFA->RE. The Best, thanks
I was reading the textbook like crazy and could not understand it at all but your video allowed me to grasp this much better . Thank you so much!!
Thank you soooo so much!! I didn't understand what my professor was doing in the lecture because he didn't explain what he did and why he did it. You saved me !
Finally, I found a clear explanation for these kinds of questions, thank you.
You're welcome!
im gonna buy you an eraser
thank you for the videos saving me in college
اقسم بالله فنان اول مره افهم التحويل بالسهولة دي ❤❤❤ Thanks. Your explanation is amazing
albeeeeey
My textbook's explanation for this was terrible, thank you so much this made so much sense!
You're very welcome!
Huge thanks for this example. A much better explanation than my professor!
You're very welcome!
I have a midterm tomorrow and this video literally are saving me!! thank you
You explained it better than my college professor. U are amazing.
broo you really simplified it for me. thank you for saving me hours of unnecessary studying 👏
Really good video! Love the way you break things down into normal English. Appreciate it!
Incredible. You are a great professor. I like it when you put it into steps. It is really easy theory. I think the biggest challenge is just explaining it and you do a very good job at it.
Thank you so much. This is the easiest one to understand among all the other videos about this.
Thanks!
Such a vivid and clear explanation ! Thank you so much for making this
Thanks so much! Don't forget to check out our theory lectures series playlist.
Marvelous video for DFA to regex! thx! I cant find such a vivid teaching video on Chinese Internet at all!
the best video i found, thanks, hello from spain
Very nicely explained, thanks from Sweden!
Simon very welcome!
OMG! This is a lot easy than the language in the book. Thanks!
WOW !! thanks a lot! I have an exam soon and it was very helpful!!!
i love you so much, all your videos make so much sense and it will be the reason i pass this class
best method that I ever seen! thanks for the explanation!! thank you so much ^^
AGA you're very welcome!
Damn nice vid man!
Agreed! Lmfao
You are AWESOME! I am so so glad I found your channel!
Thanks a ton! got more out of this 14 min than the 1 hour lecture
Many thanks. I owe my Automata & Compiler paper's credits to you
Finally, I got it. Thank you very much.
Thank you so much! 😊
I've finished the implementation of this using the IN-OUT trick 🥳
Thank you so much! I have review the lecture and read the book more than 2 hours in order to undertand the GNFA, but I failed. I have watched this video about 7 mins, I figured it out.
Thanks very much! Make sure to watch the other theory videos I've made
Love this
RIP Kleene Algorithm and Ardens rule
lol, relatable
Thank you so much! You are gifted at teaching!
You are the best! I almost spend 2 hours to understand the ripping from the theory of computation book :(
Glad to help!
Thank you so much. you are saving me in my discrete 2 class.
it was helpful & clear, you saved my time & life😀thanks
Super Sir
ALMIGHTY bless you with all kinds of wealth
ILL SAY IT AGAIN YOU ARE THE GOAT!
Very good explanation. Thank you!
You're welcome!
Thank you so much for making this!! Such a clear explanation!
Thank you very much this has helped me understand how to use GNFA.
You're very welcome!
this was SO HELPFUL
sir, you are better than my professor
Lol thanks! I should be your professor instead ;) kidding.
How do you know when to combine different paths from a state to another state with a union? There were times where there were alternative paths from one state to another but they weren't included in the union. For example at 6:03, to go from q2 to F we could've taken the that q2 -> q0 -> q1 -> q3 -> F but we only chose the path shown in the video. I'm not sure if this is just intuition or there is some algorithmic and definitive way of doing this. At 7:15 you did a union here but I'm not sure why union wasn't done in the other case I mentioned?
In other words how do you know which paths to choose to get from one state to another? There are some other paths you could've taken from one state to another but chose not to.
You don't worry about that. You only focus on length-2 paths: the ones that go through the state you're trying to remove.
This explanation was great! Thank you very much,
thank you for the explanation! really easy to follow and understand :)
You're welcome!
Thanks for this clear explanation!
wao man :) pictorial representation with great explanation makes it clearly understandable . Thanku :)
abhishek kumar you're very welcome!
You are a godsend mate
Great explanation, thank you!
dave cn you're welcome!
great video ! thanks from Germany !
Thanks for the best explanation!
Question: Is Union equivalent to "+". In my classes we use the + sign and not the U. If they are can i directly substitute to get the desired answer from my Uni?
yes
Hello this is a great technique! I had a doubt though. What to do in case we have a trap state? How to "rip" that state out? I don't see how to do this since trap state never comes in the path to final state. My gut is telling me to just ignore the path to trap state but I'm not sure if that's right.
Edit: I figured it out! Since this method is agnostic to whether this is a DFA or NFA, we can just ignore the trap states before hand!
I had the same question. Thank you for coming back to your own question
What if my start state is also my final state?
Great explanation, thank you so much.
You're welcome!
Excellent video, too bad it doesn't have that many views
Cody Elhard thanks! I hope it can get more popular too!
Fantastic! Just one issue: the audio levels are quite low, it would be helpful if you brought them up
Thank you this was so helpful!!
Love from India❤🇮🇳
Great explanation!
Julian Rahahleh thanks Julian :)
It was really helpful and very easy
thank you!! very comprehensive
thanks for the great explanation
Sir if there is dummy state given in NFA how we treat it in converting to regular expression?
Note that there would be no outgoing transition in that case. So the number of new transitions is 0 when you rip it! :) (There is a more formal proof of that but that's the basic idea)
@@EasyTheory ok thank you sir
You’re a literal god
what do you do if the old start state is accepting? does the new start state become accepting?
thank you for this cogent explanation. I hope that dog has calmed down in the video???
yeah this video is a good one. thanks man!
Thanks very much!
Dude you're a legend
Fantastic video, thank you very much
You're welcome!
Thanks for the nice explanation. Why do you ignore the transition from q1 -> q2 -> q3 -> F when you're ripping q3? I think it doesn't make a difference but I just wonder because later you consider "longer" paths.
Because of transitivity. If we know how to get from q2 to f, then we know how to get from q1 to f because that's just concatenating the two regexes along the way.
@@EasyTheory kinda late to the party, but what if I considered this path? instead of only a*, it would be a* + (aba*)?
Same question
Great work, thanks a lot!
this is absolutely the best
Adem Çapan thanks!
do you have to remove dead states? that is, nonaccepting states that have no outgoing arrows?
Thank for the explanation
God I wish you were my professor
Awesome Video !!
Do you need to put the last part of the regular expression (a*+aba*) between parentheses?
Paul good question. It's not necessary, but I would do it if I were you, because it reduces ambiguity that some people may have.
@@EasyTheory Thank you!
this ecplanation is brilliant
Sergey Gerodes thanks!
Wow! Amazing! Ty so much :D
where should i put to new final state if there is a non-final state after a final state?
Greattt video dude!
Thank you very much for your clear explanation. I have a question though. You mentioned that you can pick any state to get started. However, elimination states in different order will likely produce a different RE. E.g. if I eliminate states in this order: q2, q1, q3, q0, I will get the result as (a(bUaa))*(a(abUe)a*), where e is epsilon. Is there a way to convert that RE to a((bUaa)a)*(a*Uaba*) which is what you get? or prove those two are basically same?
i get same result as you
You are my favorite person
thank you my prof just complicated things via using phi transition also.
why do i get a different regex when removnig q1 before q0
Great video, thanks! One question: How do I build pairs in the In-&-Out-list if there is a state with several Ins and several Outs? Do I have to treat this a cartesian product so that every In builds a pair with every Out?
It's not exactly the Cartesian product, but some kind of product, yes (it's possible to formulate it as Cartesian though - the problem lies with the results being concatenations, not ordered tuples as the Cartesian product would give.)
But yes, every "in" goes with an "out".
@@EasyTheory Thank you!
explained very well
Does this strategy work for DFAs as well?