13:48 That keyboard 💀

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

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!

Most underrated topic in CS, loved the video!

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.

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

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

Im just now realizing "Computerphile" is a pun

@MrRyanroberson1

Жыл бұрын

especially with that diagram at 6:41

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

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.

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

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.

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.

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!

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!

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!

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.

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

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

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.

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

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.

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!

nice explanation

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)

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

8 ай бұрын

I WAS just thinking that.

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!

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

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

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

Rick Wakeman has really shifted paradigm.

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

Can't NFAs have null transitions too?

Old printer paper had me triggered 😳😎.

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

10 ай бұрын

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

how can i become a non determisnistic automaton?

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

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

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

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

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

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

i can't help but point out the suggestive thumbnail

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"

I got the graph and everything up to the code where he lost me.

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

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

I think I pooped my pants around minute 12 or so

What's penultimate

@peterittzes

Жыл бұрын

second-to-last

awesome🎉

love thorsten but his python formatting is making me anxious

Why did he have to do that specific automaton 🥵

@canelonism

Жыл бұрын

wdym?

@MrRyanroberson1

Жыл бұрын

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

Im a bit Rusty on computerphile.

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!

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

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

All DFAs are NFAs but not all NFAs are DFAs

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

Perhaps someone should wash their keyboard🙈

Its doable? Its feasible 😂

please invest in a tripod

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.

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?

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.

lambda