Non-Deterministic Automata - Computerphile

Non deterministic finite state automata described and then shown in Python by Professor Thorsten Altenkirch

And here is my solution to the powerautomaton construction.

#nfa #code #python #Thorsten #automata


This video was filmed and edited by Sean Riley.

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

[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 ;)

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

[gitgudsec]

please tell me he was rocking birkenstocks + socks under the table.

[computersciencebyd-m-]

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!

[jackwest]

Most underrated topic in CS, loved the video!

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

[LassWasLernen]

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

[sewoh]

Im just now realizing "Computerphile" is a pun

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

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.

[ivanskyttejrgensen]

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.

[garysturgess]

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.

[circuitgamer]

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

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

[bmitch]

I was so confused until I looked up the definition of penultimate ("next to last" for anyone else that's confused).

[wChris_]

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

[janPeja]

"I think I can hire you as some automaton..." 🤣 not sure if compliment or roast

[griffinschreiber]

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.

[MrRyanroberson]

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.