What is an Nondeterministic Finite Automaton (NFA)?
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.
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶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.
Видео What is an Nondeterministic Finite Automaton (NFA)? канала Easy Theory
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶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.
Видео What is an Nondeterministic Finite Automaton (NFA)? канала Easy Theory
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
How Covering Arrays can Potentially Save Billions in TestingTwo Different Definitions of NP are EquivalentThe Top Reason Why I'm a ProfessorDeterministic Context-Free Languages NOT Closed Under ConcatenationBonus: A Different Ordering of the Chomsky Normal Form Conversion Algorithm?!How to check if a DFA satisfies a specification (SUB_DFA)!Introduction to the Theory of Computation (Full Course)The Hardest Exam Question I've Ever Given...So Far...Planar Machines in TheoryHow to write a Deterministic Finite Automaton formally? Example Conversion👀Context-Free Grammar (CFG) Example: 0*1*A Cute Research Problem about Context-Free GrammarsPumping Lemma for Regular Languages Example: 0ⁿ1ᵐ, n != m (HARD!)DFA Minimization ExampleMath Basics for Theory in Computer ScienceLogic: Propositions, Implication, Converse + ContrapositiveA nice problem and proof about languagesBusy Beaver #4 Turing Machine SimulationWhat are Quantifiers?Direct Proofs - how do you do it?