Here we show how to create an NFA for all substrings of a given string w. The idea is to first create an NFA for the language {w} (i.e., just w and nothing else). Then note that we can make all of the states final in this NFA, and then add epsilon-transitions for the substrings that can start "later" in the string. Note that this handles substrings, and not subsequences. Contribute: Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs Live Streaming (Saturdays, Sundays 2PM GMT): Twitch: https://www.twitch.tv/easytheory (Youtube also) Mixer: https://mixer.com/easytheory Social Media: Facebook Page: https://www.facebook.com/easytheory/ Facebook group: https://www.facebook.com/groups/easytheory/ Twitter: https://twitter.com/EasyTheory Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶ADDITIONAL QUESTIONS◀ 1. How can you modify this NFA to make one for all subsequences of w? 2. Is this the smallest NFA in terms of the number of transitions? 3. Can a loop ever be added to an NFA like this? ▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory. ▶ABOUT THIS CHANNEL◀ The theory of computation is perhaps the fundamental theory of computer science. It sets out to define, mathematically, what exactly computation is, what is feasible to solve using a computer, and also what is not possible to solve using a computer. The main objective is to define a computer mathematically, without the reliance on real-world computers, hardware or software, or the plethora of programming languages we have in use today. The notion of a Turing machine serves this purpose and defines what we believe is the crux of all computable functions. This channel is also about weaker forms of computation, concentrating on two classes: regular languages and context-free languages. These two models help understand what we can do with restricted means of computation, and offer a rich theory using which you can hone your mathematical skills in reasoning with simple machines and the languages they define. However, they are not simply there as a weak form of computation--the most attractive aspect of them is that problems formulated on them are tractable, i.e. we can build efficient algorithms to reason with objects such as finite automata, context-free grammars a ... https://www.youtube.com/watch?v=CxyUca_MuB8

Here we introduce the idea of a "generalized" general NFA method, which we call the GGNFA method. The idea is that we can generate a regex for any size NFA without having to do the conversion ourselves. We motivate this with a 3-state NFA, and are able to derive a regex that represents all possible languages that an NFA with 3 states can recognize. If we have an actual NFA we want a regex for, we just "plug in" to the "general" regex we have and then automatically get one for free. This method generalizes to any number of states and any alphabet. The main video on the conversion and its proof is here: https://youtu.be/HUolNKq7v3k #easytheory #nfa #dfa #gate #gateconcept #theoryofcomputing #turingmachine #nfatoregex #cfg #pda #undecidable #ricestheorem Contribute: Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs Live Streaming (Sundays 2PM GMT, 2 hours): Twitch: https://www.twitch.tv/easytheory (Youtube also) Social Media: Facebook Page: https://www.facebook.com/easytheory/ Facebook group: https://www.facebook.com/groups/easytheory/ Twitter: https://twitter.com/EasyTheory Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 Gold Supporters: Micah Wood Silver Supporters: Timmy Gy ▶ADDITIONAL QUESTIONS◀ 1. Try (if you dare!) to derive the regex for 4 or more states ;) 2. If I have a regex R for n states, can I get one for n+1 states from R? ▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=u_R0tZAnTi4