Professor Thorsten Altenkirch is so good at explaining things and the passion he has for the subject matter really shows! As a side note: please add the name of the presenter to future videos (or at least put more than just a hashtag with their first name in the description). Cheers!
@Computerphile Жыл бұрын
Fair point, a genuine mistake not to put his name in the description -Sean
@KraylusGames Жыл бұрын
@@Computerphile No worries, thanks!
@dickheadrecs Жыл бұрын
this channel is so awesome. still going strong 💪 please never stop. it’s so nice having this little tidbits delivered to you in such a friendly conversational way
@andrewjknott Жыл бұрын
To increase clarity of communication, do not reuse symbols. Instead of using numbers for both tokens of the language {0,1} and labels for the NFA&DFA states {0,1,2}, use letters {a,b,c} for one and numbers for the other.
@SimGunther Жыл бұрын
There's some algorithms that can translate NFAs into DFAs, but using Arden's Theorem allows you to translate the NFA into a regex which supposedly is "more maintainable" depending on the NFA in question. That regex in question can be represented as a table driven DFA for max speed at the cost of auxiliary space which can be minimized with Hopcroft's algorithm. Of course, you could just create a DSL for NFAs and have a code generator which creates the DFA for you ;)
@tpog1 Жыл бұрын
"That's BTO. They were Canada's answer to ELP. Their biggest hit was TCB. That was how we talked in the seventies. We didn't have a moment to spare." - Homer Simpson.
@Ceelvain Жыл бұрын
This equivalence between NFA and regex also shows that for every FSA there's an equivalent planar NFA. No matter how convoluted the original automaton is. Although, I doubt there's much use for this property. 😅
@avramcs Жыл бұрын
@@Ceelvain well that’s kind of obvious and trivial. Since DFAs and NFAs are equal in power and with DFAs working to provide a system for a regular language, it’s pretty obvious to see that any FSA can be translated to a DFA or NFA, since they literally couldn’t be anything else
@Ceelvain Жыл бұрын
@@avramcs the keyword was *planar*. As in planar graph.
@sewoh100 Жыл бұрын
Im just now realizing "Computerphile" is a pun
@MrRyanroberson1 Жыл бұрын
especially with that diagram at 6:41
@jackwest540 Жыл бұрын
Most underrated topic in CS, loved the video!
@JNCressey Жыл бұрын
8:07 The example walking through "111" only read two iterations Start: coin on 0 First "1": the coin on 0 goes to 0 and 1. Second "1": the coin on 0 goes to 0 and 1, and the coin on 1 goes to 2. Then you stopped before reading the third "1" of the input.
@ThorstenAltenkirch Жыл бұрын
Oops, sorry.
@TheWombatGuru Жыл бұрын
@@ThorstenAltenkirch But it would still have worked right, in the next iteration the final coin would have vanished and the coin in position 1 would go to the final position!
@computersciencebyd-m-3323 Жыл бұрын
Automata theory may seem simple at first, but its power is phenomenal! The deeper you dive, the more mind-blowing it becomes. Get ready for a thrilling journey into the world of computation!
@faanross Жыл бұрын
please tell me he was rocking birkenstocks + socks under the table.
@briancollins1149 Жыл бұрын
even better. the continuous form printer paper.
@Leaving_Orbit Жыл бұрын
Hahaha
@HerrLavett Жыл бұрын
Birkenstocks and socks are great
@briancollins1149 Жыл бұрын
@@HerrLavett unless yer the sock
@dickheadrecs Жыл бұрын
Thorsten is a real one 👡 🔧
@LassWasLernen Жыл бұрын
NFA‘s and DFA‘s can‘t be explained smoother than that. Mr. Altenkirch rocks! Grüße aus Deutschland :-)
@ivanskyttejrgensen7464 Жыл бұрын
Nice explanation. I knew DFA, but hadn't considered NFA. It' a shame that FSAs are usually only taught in combination with pattern matching or network protocols. I've found them useful in a few other scenarios.
@user-yv1qs7sy9d Жыл бұрын
Also, this kind of NFAs is equivalent to the NFAs that can the transition relation is defined for the empty string, ε, which is also a very interesting case.
@janPeja Жыл бұрын
"I think I can hire you as some automaton..." 🤣 not sure if compliment or roast
@esra_erimez Жыл бұрын
How does this comment not have more likes???
@DavidLindes8 ай бұрын
I don't know what it is -- if it's something about Thorsten's approach, or just timing with where my energy levels are, or what, but this video and the last one are I think the first Computerphile videos where I've actually gone through and written code (copying what's on the screen, but then writing some of my own... (though I admit I didn't finish minimize for DFAs. But I might get back to it?? Anyway, I did the DFA-from-NFA code, and I _believe_ it's correct! Fun!
@bmitch3020 Жыл бұрын
I was so confused until I looked up the definition of penultimate ("next to last" for anyone else that's confused).
@peterittzes Жыл бұрын
Yep, "penultimate" means second-to-last, and for maximum pretentiousness you can also use "antepenultimate" for the one before that.
@redjr242 Жыл бұрын
@@peterittzes Lol. I only heard these words used in the context of stressed syllables, e.g.: a stress and the ante-penult. Don't think I've heard it in other contexts though
@circuitgamer7759 Жыл бұрын
One of my first thoughts with this: If states were defined by locations in memory rather than tracking a number for the state or something like that, would DFAs be more processor efficient but less memory efficient, and NFAs be more memory efficient but less processor efficient (I'm mainly just checking if there are edge cases that I missed through an analogy)? DFAs would only have to check a few paths from any given state, but NFAs would have to check every path from every active state. At the same time, DFAs would have more individual states than NFAs. (to remove a bit of ambiguity with the way I phrased that, I'm specifically wondering if there's cases where those aspects are both reversed. There's definitely cases where they are the same, or maybe when one aspect is reversed, but I'm wondering about cases where both are reversed.)
@yeoldestuff Жыл бұрын
That's precisely the case, if an NFA has n states, then the equivalent DFA would have 2^n states which means that the memory requirements of the DFA are exponentially higher
@garysturgess6757 Жыл бұрын
I remember ages ago doing a unit on CourseRA (when it was all still free) that went over DFAs, NFAs, all the way up to Turing Machines. One of the most fun courses I ever did - this is great stuff.
@welcometothemadhouse Жыл бұрын
I was interested in Automata theory and how machine learning was developed in part from automata theory. It is brilliant to see how such as abstract thing is (usually) so fundamental to our world now!
@wChris_ Жыл бұрын
Great explanation of a topic i had to learn for (Theoretical) Computer Science!
@griffinschreiber68676 ай бұрын
This reminds me of when I tried to make a program to save/load data to/from a human-readable file. I realized that I was in essence just building a compiler for the file encoding format I had created -- even though it wasn't Turing complete.
@mattwilkinson7079 Жыл бұрын
Why did this have to come out AFTER my exam on formal language theory 😂
@Paul-sk7px Жыл бұрын
Can I be the first to point out Prof Altenkirch's striking resemblance to the Trainman in Matrix Revolutions? I mean he could actually be him for all I know. It genuinely wouldn't surprise me.
@ramses_mars Жыл бұрын
Haha. That role was played by New Zealand actor Bruce Spence.
@aman-qr7wh8 ай бұрын
I WAS just thinking that.
@MrRyanroberson1 Жыл бұрын
13:38 i might suggest a more intelligent upper bound which is 2^(states - entry states) number of states since all entry states are always present in the NFA, which we see here because your 4 are the most possible states that you could reach from a 3-state with one entry point.
@DeathlyTired Жыл бұрын
At first, I read the titIe as, "Non-Deterministic Stigmata". 'That's a departure for this channel', I thought
@AcornElectron Жыл бұрын
Rick Wakeman has really shifted paradigm.
@mrlithium69 Жыл бұрын
he makes his number 1's look like upside down V's
@TomiTapio Жыл бұрын
Non deterministic video game AI? Character states like idle wandering, scared, fleeing, attack, defend, move towards allies. Input for state change is multivariable, and add a random dice roll chance for state change...
@HomeofLawboy Жыл бұрын
At 8:27 it shouldn't have finished because the input wasn't fully consumed
@MatejDujava Жыл бұрын
There should be one more read, but the state "coins" would end up in same positions, (coin on 2 will disappear, coin move from 1 to 2, from 0 to 1, and "duplicate" on 0) this transition is shown at 11:55
@HomeofLawboy Жыл бұрын
@@MatejDujava yes
@habibie Жыл бұрын
Old printer paper had me triggered 😳😎.
@hri7566 Жыл бұрын
i can't help but point out the suggestive thumbnail
@cryptotharg7400 Жыл бұрын
How can a computing system be non-deterministic, without taking in some random variables from the environment?
@mrlithium69 Жыл бұрын
"magic" he said it 3 times
@SplendidKunoichi Жыл бұрын
not doing what its supposed to do, no one actually knowing what its supposed to do, not halting, the usual the idea if you like is that it gets multiple tries to agree with a deterministic result then whats non-deterministic is how many it actually took
@EdwardTheLegend Жыл бұрын
Ah yes love a good old exercise for the reader. 👍
@cryptotharg7400 Жыл бұрын
This guy is probably going to take over the world, at some point.
@mrlithium69 Жыл бұрын
I thought "im glad this is what he's doing instead of being evil"
@xybersurfer Жыл бұрын
nice explanation
@dominiquefortin5345 Жыл бұрын
I had never thought of using a breath first search to do NFAs.
@leroyladyzhensky210 Жыл бұрын
I think I pooped my pants around minute 12 or so
@arandomperson8336 Жыл бұрын
I think regular expressions is where I realized I wasn't cut out to be a programmer
@ommadawnDK Жыл бұрын
👍🏻👍🏻👍🏻 Could this have been done where the inputs and the states didn't use the same symbols?
@unchaynd7266 Жыл бұрын
Can't NFAs have null transitions too?
@mushengu Жыл бұрын
Return that to the file it was it opens a new symbol binary..
@wingedtoast7495 Жыл бұрын
if someone could explain to me why it's okay for a state to just disappear that'd be cool (unless it's just like implied it collapses back to state 0 for example idk my brain wants to rearrange it into a different thing)
@InShadowsLinger Жыл бұрын
I got the graph and everything up to the code where he lost me.
@Anomyos Жыл бұрын
After I have seen some in-game working computers made in Minecraft it raised a few questions: What is the most effective virtual processor currently and if the virtual processor ever reaches over 100% efficiency over its physical counterparts on which it is running would not there be potentially a processor with infinite processing power? What would be the challenges in that system? I tried to google the answer, but I think either my current terminology on the subject is not advanced enough or there have not been any attempts even to try it because it seems so obliviously not possible for capable people. I wish I could least some lead to find an answer.
@kennythegamer1 Жыл бұрын
hmm, I'll ask anyway. What do you mean by "the virtual processor ever reaches over 100% efficiency over its physical counterparts on which it is running"?
@TorvicIsSanta11 ай бұрын
@@kennythegamer1 I think they might mean if you simulated/emulated more processors than the hardware that the simulation is running on? Of course, if that is what they mean then the answer is that the simulation is dividing the additional workload between multiple clock cycled on a single thread
@superhussein Жыл бұрын
how can i become a non determisnistic automaton?
@canelonism Жыл бұрын
love thorsten but his python formatting is making me anxious
@user-fp3eb8cc9u3 ай бұрын
Thanks, can you give me an example in c langage please!!
@MrMcsoftware Жыл бұрын
Would you or a viewer please explain how you would use the DFA NFA converter (in terms of python programming)? I tried: N2=D0.NFA which didn't complain, but when I tried to use N2, it complains there's no run procedure. Python isn't my main language. It may be obvious to someone who programs python all the time 😀
@MrMcsoftware Жыл бұрын
I think I figured it out myself: N2=DFA.NFA(D0) and it needs to be after both classes. Is that right? It seems to work.
@ThorstenAltenkirch Жыл бұрын
@@MrMcsoftware It should be enough to say N2=NFA(D0).
@MrMcsoftware Жыл бұрын
@@ThorstenAltenkirch If I leave off the "DFA." part, it complains about 4 missing parameters (it thinks NFA is referring to the class and not the method in DFA). Maybe you have a newer version of python that can figure that out.
@ThorstenAltenkirch Жыл бұрын
@@MrMcsoftware Sorry, I got mixed up. I meant D0.NFA()
@MrMcsoftware Жыл бұрын
@@ThorstenAltenkirch That works. Thanks!
@moistness482 Жыл бұрын
Why did he have to do that specific automaton 🥵
@canelonism Жыл бұрын
wdym?
@MrRyanroberson1 Жыл бұрын
yes i saw it too immediately, it's so spicy
@prose_mozaic Жыл бұрын
Would it at all be possible for me to intern under you? I truly would love to learn as much as I can on these subjects!!
@cakewolf44 Жыл бұрын
no
@SRWeaverPoetry Жыл бұрын
Im a bit Rusty on computerphile.
@normanpinto Жыл бұрын
Why is there a keyboard on his desk?
@user-yv1qs7sy9d Жыл бұрын
So he can type, of course! (Yes, I saw both types of keyboards)
@c1ph3rpunk Жыл бұрын
I have a feeling he’s DJ’ing at an EDM club in Berlin over the weekend.
@jeffreyokun2355 Жыл бұрын
Good question, I would have assumed this guy simply draws the commands on a printer paper and feeds them into the computer...
@siddharthsingh7281 Жыл бұрын
What's penultimate
@peterittzes Жыл бұрын
second-to-last
@krox477 Жыл бұрын
All DFAs are NFAs but not all NFAs are DFAs
@Brunoenribeiro Жыл бұрын
I need to admit: this didn't make any sense to me on the first try 😅 I rewatched until it clicked. Strong monad vibes to me in this one!
@Haaknes Жыл бұрын
Perhaps someone should wash their keyboard🙈
@sam-sn5pu Жыл бұрын
please invest in a tripod
@EdwardTheLegend Жыл бұрын
awesome🎉
@NickCarterPoops Жыл бұрын
OMG! Will this 132 column paper writing ever stop in this chnnel. The man had a laptop next to him! use the output! This is so backwards!!
@ScorpioneOrzion Жыл бұрын
and those sets of states can be just 2^n states, each representing a set of states.
@kgm1000uk Жыл бұрын
Its doable? Its feasible 😂
@avi12 Жыл бұрын
Am I the only one who only understands 20% of what he says?
@jeffreyokun2355 Жыл бұрын
Perhaps, because I could only understand 0.1%
@ivanskyttejrgensen7464 Жыл бұрын
Probably
@xybersurfer Жыл бұрын
i didn't care that much for the python code, but what wasn't clear?
@nobackupkiwi Жыл бұрын
Everything in the universe is deterministic.
@1ucasvb Жыл бұрын
"... probably"
@nobackupkiwi Жыл бұрын
@@1ucasvb it is
@1ucasvb Жыл бұрын
@@nobackupkiwi How do you know?
@nobackupkiwi Жыл бұрын
@@1ucasvb I know it, I'm just better.
@dipi71 Жыл бұрын
15:45 Please don't use italic together with coding fonts -- or use a proper code editor that can actually render italic text without clipping outside the glyphs' bounding boxes. It physically causes me pain to look at all those »self.« references. On the other hand, it's just some anemic Python code, and you're not even using dark mode. Oh well.