ε-closure: what is it? (epsilon closure)
Vložit
- čas přidán 7. 09. 2024
- Here we look at ε-closure (or epsilon closure), which is important in the NFA to DFA conversion process. The basic idea is to consider a set of states, and every set of states "reachable" from that set (including the original) using only ε-transitions. We give several examples as well.
Contribute:
Patreon: / easytheory
Discord: / discord
Live Streaming (Sundays 2PM GMT, 2 hours):
Twitch: / easytheory
(CZcams also)
Mixer: mixer.com/easy...
Social Media:
Facebook Page: / easytheory
Facebook group: / easytheory
Twitter: / easytheory
Merch:
Language Hierarchy Apparel: teespring.com/...
Pumping Lemma Apparel: teespring.com/...
If you like this content, please consider subscribing to my channel: / @easytheory
Ultimate Supporters: (none)
Diamond Supporters: (none)
Platinum Supporters: (none)
Gold Supporters: Anonymous (x1), Micah Wood, Ben Pritchard
Silver Supporters: Timmy Gy
Supporters: Yash Singhal
▶ADDITIONAL QUESTIONS◀
1. Can the ε-closure ever be empty?
2. What is the ε-closure of a state in a DFA?
▶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 and pushdown automata. For example, we can model a piece of hardware (a circuit) as a finite-state system and solve whether the circuit satisfies a property (like whether it performs addition of 16-bit registers correctly). We can model the syntax of a programming language using a grammar, and build algorithms that check if a string parses according to this grammar.
On the other hand, most problems that ask properties about Turing machines
are undecidable. This CZcams channel will help you see and prove that several tasks involving Turing machines are unsolvable---i.e., no computer, no software, can solve it. For example, you will see that there is no software that can check whether a
C program will halt on a particular input. To prove something is possible is, of course, challenging. But to show something is impossible is rare in computer
science, and very humbling.
Next video! NFA to DFA powerset construction: czcams.com/video/PPiebTISJBk/video.html
Such a wonderful explanation. Thanks a bunch❤
Great explanation. Thank you!
You're welcome!
My goal for today and tomorrow is to watch all 146 videos in the series LOL. Thanks a lot for all the informative videos. Good luck with my final exam! :(
146 videos in 2 days... Not possible
Thank you. Finally, I understand it 🤩
Good point mentioned 10:40 THANKS,
Thank you!
thx dawg
Thanks very much!
thanks
Life saver
Thank you so much I understood it, but do you have a video about Extending the transition function for strings in NFA or Epsilon NFA, because my professor confuse us with symbols and we don't understand anything .
The idea of that is to define what would happen if we fed a whole string from a state instead of just a character or epsilon. I don't have a vid on it but basically delta^(q, x) is the set of all strings that q can reach after reading all of x. For a DFA, this is exactly one state, but for an NFA it is a bunch of states possibly. So the commonly used definition here defines delta^(q,x) in terms of prefixes of x. In other words, if x is equal to wa where a is a character, then delta^(q,x) is the same as delta^(q,w) but then the states reachable from that by reading an a afterwards.
@@EasyTheory he uses something like this:
δ“hat” (q0,wa) = {r:∃P∈δ“hat”(q0,w); r∈δ(q0, a)}
i know it's that q0 is the initial state and delta hat is used for strings and x is the string and w is the prefix and a is the last letter and P is the subset of the Q set
but why there's r and the backwards E, i would really appreciate it if you make a video about those, and thanks for the reply.
@@kolibri5861 I think the last q0 should be P, but essentially yes - it's a recursive definition. Assume you know all the states you can see from q0 after reading w; then look at all the states from those after reading one more character a. The state P here is the one after reading w, and r is after reading an a. We have the "in" set operator here because the NFA may have many states that one can see after reading something.
@@EasyTheory yes sorry it's P, i looked every textbook on the web none of them explained it that well, thanks you are a gift from god, keep it up :) .
555
556