Here we ponder the question about what is "necessary" for a state-based machine to recognize the concatenation of two regular languages (or the star of one). We realize that we only need "epsilon" transitions to be able to "instantaneously" jump from one state to another, as well as allow for "nondeterminism". We call these NFAs (nondeterministic finite automata), and we show that we can achieve concatenation and star really easily with them (and even union!). The problem is that they are not the same thing as DFAs, and in a future lecture we will show equivalence.
Contribute:
Patreon:
https://www.patreon.com/easytheoryDiscord:
https://discord.gg/SD4U3hsLive Streaming (Sundays 2PM GMT, 2 hours):
Twitch:
https://www.twitch.tv/easytheory(Youtube also)
Mixer:
https://mixer.com/easytheorySocial Media:
Facebook Page:
https://www.facebook.com/easytheory/Facebook group:
https://www.facebook.com/groups/easytheory/Twitter:
https://twitter.com/EasyTheoryMerch:
Language Hierarchy Apparel:
https://teespring.com/language-hierarchy?pid=2&cid=2122Pumping Lemma Apparel:
https://teespring.com/pumping-lemma-for-regular-langIf you like this content, please consider subscribing to my channel:
https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1Ultimate 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. Can you make an NFA for all strings that contain 011 as a substring? How many states are needed?
2. How small can an NFA be comparatively to a DFA for the same language? (Try working out small examples).
▶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
...
https://www.youtube.com/watch?v=P5iWwYtwlwg