How many computations are there in an NFA?

Here we look at the question of how many computations there are in a nondeterministic finite automaton (NFA). It turns out to be a very surprising answer, because NFAs allow for multiple transitions, epsilon transitions, and even missing transitions, which DFAs don't allow for any of them. We also then show that the same idea for closure under complement for DFAs does not work for NFAs.

Contribute: 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) 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

Ultimate Supporters: (none) Diamond Supporters: (none) Platinum Supporters: (none) Gold Supporters: Anonymous (x1), Micah Wood, Ben Pritchard Silver Supporters: (none) Supporters: Yash Singhal

▶ADDITIONAL QUESTIONS◀

1. Is there an NFA that isn't a DFA for which closure under complement DOES work?
2. How big can a "complement" NFA be compared to the original?

▶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 asp ... https://www.youtube.com/watch?v=DtdtlPh_QzU