ฝัง
- เผยแพร่เมื่อ 4 ก.ค. 2024
- How are nondeterministic finite automata (NFAs) different from DFAs? This video provides an introduction to NFAs, also one of the simple computational models and another kind of finite state machine.
____________________
Additional resources:
• Regular Languages: Det...
- My previous video on finite state machines and DFAs. Understanding what finite state machines are exactly will be very helpful in learning about NFAs!
• Introduction to Langua...
- I made a video on languages if you don't know what languages are.
Michael Sipser. 2006. Introduction to the Theory of Computation (2nd. ed.). International Thomson Publishing.
- The main source of my Theory of Computation knowledge (a textbook). Read Chapter 1.2: Nondeterminism to learn more about NFAs.
_____________________
And as always, this video project could not have been done without the support and guidance of Audrey St. John at Mount Holyoke College, a truly incredible professor-mentor-human.
![[Full Episode] MasterChef Junior Thailand มาสเตอร์เชฟ จูเนียร์ ประเทศไทย Season 3 Episode 4](http://i.ytimg.com/vi/e7Oqqo90x_w/mqdefault.jpg)
Yeah this is good learning. College is suffering and I understand not everyone can possess such gifts and talents, so thank you kindly for allowing us to witness yours.
100 times easier/more enjoyable for me to learn from these videos than from a university lecture....thank you
hey i'd just like to thank you for saving my semester
hey, these videos are GREAT
Your way of explaining both DFAs and NFAs is very clear and concise, thank you so much! :)
thank you! Take my heart ❤ . Please make regular expression and it how to represent it as an nfa in next video. And again thank you so much for the effort !
i always find it difficult when the professors goes with the bookish description.... like learning the basic and understanding the topic is the base of your solution. thank you very much and please keep doing what you do!
I'll get my whole college class to watch your playlist I Loved it
Your channel is helping me graduate. Thank you so much!
This is a gold mine. Thank you for making this.
Theoretical computer science helps us put limits on computation; If it cannot happen in the theoretical models, then it cannot happen in real life. Lydia does an AMAZING job at this. You are a gifted teacher Lydia!
Awesome video, please do more. Thanks.
such a good work!! Thank you very much
Thanks for the videos, explained very well
I saw all your videos...👌👌👌
you made it very easy to understand
The video provides an in-depth explanation of Nondeterministic Finite Automata (NFAs) in contrast to Deterministic Finite Automata (DFAs). Here's a summary of the main points discussed:
Definition and Differences: NFAs, unlike DFAs, can transition into zero or more states for each symbol in the input. This characteristic makes them nondeterministic, as their next state is not always predetermined.
Examples and Acceptance Criteria: The video illustrates this concept through examples, including an NFA that accepts strings containing a '1' in the third position from the end. It highlights a key feature of NFAs: a string is accepted as long as there exists at least one path to an accept state, regardless of other possible paths that might lead to rejection.
Transition on Empty String: NFAs can also transition on the empty string, meaning they can change states without consuming any input symbols. This adds flexibility in constructing NFAs for certain languages.
Formal Definition: NFAs are defined as five-tuples, similar to DFAs, but with a transition function that can output a set of possible states instead of just one. This allows for multiple potential pathways through the automaton for a given input string.
Equivalence with DFAs: Despite the structural differences, the video concludes that NFAs are not more powerful than DFAs. Any language recognized by an NFA can also be recognized by a DFA, meaning both can define the same set of regular languages. NFAs offer a more simplified construction for certain languages without increasing the computational power beyond that of DFAs.
This explanation underscores the theoretical underpinnings of finite automata in computer science, particularly in the areas of language recognition and automata theory.
fascinating video
Hey how come you stopped making videos? Your videos are so clear and easy to understand.
Well done 👍🏻
03:00 yes it accepts single "1" but; It will also accept any input sequence that contains "1". Because of the unweighted path between starting node q0 and q4, anytime when you take "1" there will be a path to q5 which is a final state. So the condition of "1 in the third final position" becomes kind of inefective.
Yes I agree. There's a flaw in the NFA since it will not only accept 1 but will also accept the strings 11, 011 or 0101, which do not satisfy the language.
No it won't accept the all strings that contain 1 but the only ones which ends with 1
Learned a lot thank
thanks you saved my grade!
Thank you 🙏
Thank you!!!!! Could you make one for converting NFA to DFA??
thank you so much
Can you explain the subset costruction algorithm? Thank you
you have saved me hours with scripts I do not understand. A question: why would DFA be used if there are NFAs? wouldn't that be always easier?
Eres la mejor
if an empty string is given as an input then the automata should directly jump to accept state looking at it, but it has two steps q4 and then q5. But where does the 1 input come in an empty string to take it from q4 to q5
Very calm and cute voice hope you are doing good in life
what is the input used for transition from q0 to q4 ?
paying for university courses to come learn on youtube instead. smh. super helpful!
the dfa doesn't accept 1110100 but i think it's in the language.
at 00:41, isn't this actually an NFA since there are several states which transition on both: 0,1 ? I thought a DFA must only transition on 1 or 0?
The video answered my question - an NFA actually can remain in the same state on 1, OR transition on 1. Great videos, I hope you make more! You have a talent for teaching.
0:38 Hmm, it doesn't accept 010100
Been following from the first video but somehow, I've failed to understand this😢
Design a deterministic finite automata
Man I've been trying to put my finger on your accent since the beginning of the series, and I think I finally got it. You grew up in India, but studied abroad/moved to the U.S., or work really hard to neutralize your indian accent.
DId I get it right? 😜
Great series, btw
bro its pronounced aksept not assept