Non-Deterministic Automata - Computerphile

[@KraylusGames]

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!

[@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.

[@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!

[@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!

[@gitgudsec]

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 👡 🔧

[@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

[@6c3333]

13:48 That keyboard 💀

[@DavidLindes]

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!

[@jackwest540]

Most underrated topic in CS, loved the video!

[@ΝίκοςΙστοσελίδα]

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.

[@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.

[@LassWasLernen]

NFA‘s and DFA‘s can‘t be explained smoother than that. Mr. Altenkirch rocks! Grüße aus Deutschland :-)

[@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!

[@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.

[@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???

[@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

[@griffinschreiber6867]

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.

[@wChris_]

Great explanation of a topic i had to learn for (Theoretical) Computer Science!

[@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

[@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-qr7wh]

I WAS just thinking that.

[@DeathlyTired]

At first, I read the titIe as, "Non-Deterministic Stigmata". 'That's a departure for this channel', I thought

[@mattwilkinson7079]

Why did this have to come out AFTER my exam on formal language theory 😂

[@hri7566]

i can't help but point out the suggestive thumbnail

[@mrlithium69]

he makes his number 1's look like upside down V's

[@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.

[@AcornElectron]

Rick Wakeman has really shifted paradigm.

[@dominiquefortin5345]

I had never thought of using a breath first search to do NFAs.

[@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"

[@arandomperson8336]

I think regular expressions is where I realized I wasn't cut out to be a programmer

[@xybersurfer]

nice explanation

[@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

[@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...

[@ommadawnDK]

👍🏻👍🏻👍🏻 Could this have been done where the inputs and the states didn't use the same symbols?

[@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"?

[@TorvicIsSanta]

@@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

[@nikosneely1558]

I wish these had closed captions 😢

[@EdwardTheLegend]

Ah yes love a good old exercise for the reader. 👍

[@habibie]

Old printer paper had me triggered 😳😎.

[@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

[@canelonism]

love thorsten but his python formatting is making me anxious

[@unchaynd7266]

Can't NFAs have null transitions too?

[@mushengu]

Return that to the file it was it opens a new symbol binary..

[@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!

[@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.

[@moistness482]

Why did he have to do that specific automaton 🥵

[@canelonism]

wdym?

[@MrRyanroberson1]

yes i saw it too immediately, it's so spicy

[@superhussein]

how can i become a non determisnistic automaton?

[@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!

[@étudiantedjaa]

Thanks, can you give me an example in c langage please!!

[@SRWeaverPoetry]

Im a bit Rusty on computerphile.

[@krox477]

All DFAs are NFAs but not all NFAs are DFAs

[@amirsync]

Why do they write on paper with markers? It's really irritating.

[@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

[@ScorpioneOrzion]

and those sets of states can be just 2^n states, each representing a set of states.

[@leroyladyzhensky210]

I think I pooped my pants around minute 12 or so

[@siddharthsingh7281]

What's penultimate

[@peterittzes]

second-to-last

[@EdwardTheLegend]

awesome🎉

[@sam-sn5pu]

please invest in a tripod

[@normanpinto]

Why is there a keyboard on his desk?

[@ΝίκοςΙστοσελίδα]

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...

[@Haaknes]

Perhaps someone should wash their keyboard🙈

[@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.

[@kgm1000uk]

Its doable? Its feasible 😂

[@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.

[@Armando51roosters]

lambda