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.
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 !
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!
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.
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!
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, helped my understanding a lot. I was just wondering what happens if the only outgoing state is itself, do we just ignore it as it cannot lead us to the final state (this is not the final/accept state).
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.
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".
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?
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.
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.
College professor spent 2 hours explaining this. Watched this video on double speed in 7 minutes.
Lmao good!
Your tuition money at work
agree
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!
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 !
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!
Didn't understand anything from my professor's book, watched this and understood everything thanks !
This is a fantastic explanation. The In/Out decomposition really helped!
You're welcome!
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!
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!!
اقسم بالله فنان اول مره افهم التحويل بالسهولة دي ❤❤❤ Thanks. Your explanation is amazing
albeeeeey
im gonna buy you an eraser
thank you for the videos saving me in college
Finally, I found a clear explanation for these kinds of questions, thank you.
You're welcome!
My textbook's explanation for this was terrible, thank you so much this made so much sense!
You're very welcome!
Very nicely explained, thanks from Sweden!
Simon 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 👏
Marvelous video for DFA to regex! thx! I cant find such a vivid teaching video on Chinese Internet at all!
Huge thanks for this example. A much better explanation than my professor!
You're very welcome!
WOW !! thanks a lot! I have an exam soon and it was very helpful!!!
Thank you so much! 😊
I've finished the implementation of this using the IN-OUT trick 🥳
Thank you so much. This is the easiest one to understand among all the other videos about this.
Thanks!
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.
Really good video! Love the way you break things down into normal English. Appreciate it!
the best video i found, thanks, hello from spain
OMG! This is a lot easy than the language in the book. 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.
Super Sir
ALMIGHTY bless you with all kinds of wealth
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
i love you so much, all your videos make so much sense and it will be the reason i pass this class
Finally, I got it. Thank you very much.
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
Love this
RIP Kleene Algorithm and Ardens rule
lol, relatable
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 gifted at teaching!
You are AWESOME! I am so so glad I found your channel!
it was helpful & clear, you saved my time & life😀thanks
Damn nice vid man!
Agreed! Lmfao
Very good explanation. Thank you!
You're welcome!
Thank you so much. you are saving me in my discrete 2 class.
best method that I ever seen! thanks for the explanation!! thank you so much ^^
AGA you're very welcome!
Thank you very much this has helped me understand how to use GNFA.
You're very welcome!
this was SO HELPFUL
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
sir, you are better than my professor
Lol thanks! I should be your professor instead ;) kidding.
You are a godsend mate
ILL SAY IT AGAIN YOU ARE THE GOAT!
Great explanation, thank you!
dave cn you're welcome!
Thanks for this clear explanation!
Fantastic! Just one issue: the audio levels are quite low, it would be helpful if you brought them up
Excellent video, too bad it doesn't have that many views
Cody Elhard thanks! I hope it can get more popular too!
Thank you so much for making this!! Such a clear explanation!
This explanation was great! Thank you very much,
Thanks for the best explanation!
great video ! thanks from Germany !
Great explanation!
Julian Rahahleh thanks Julian :)
It was really helpful and very easy
Thank you this was so helpful!!
Great explanation, thank you so much.
You're welcome!
wao man :) pictorial representation with great explanation makes it clearly understandable . Thanku :)
abhishek kumar you're very welcome!
thank you for the explanation! really easy to follow and understand :)
You're welcome!
thanks for the great explanation
thank you!! very comprehensive
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
thank you for this cogent explanation. I hope that dog has calmed down in the video???
Amazing video, thank you.
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
Love from India❤🇮🇳
Great video, helped my understanding a lot. I was just wondering what happens if the only outgoing state is itself, do we just ignore it as it cannot lead us to the final state (this is not the final/accept state).
yeah this video is a good one. thanks man!
Thanks very much!
Thank for the explanation
You’re a literal god
thank you my prof just complicated things via using phi transition also.
this ecplanation is brilliant
Sergey Gerodes thanks!
Dude you're a legend
this is absolutely the best
Adem Çapan thanks!
God I wish you were my professor
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.
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!
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
Great work, thanks a lot!
You are my favorite person
explained very well
Awesome Video !!
Wow! Amazing! Ty so much :D
you are unique one
Great video sir
Thanks!
What if I have multiple final states? Let's say q3 and q2 are finital state, then both goes to F?
Love from India!!!
lots of love ❤❤💐💐
Greattt video dude!
Perfect, thank you
so helpful, thanks