Theory of Computation was one of the most challenging but also the most fascinating courses I have ever done. It's like a theory on how computer "computes" and what computers can and cannot do.

Yay a Professor Altenkirch video, by far my favourite.

The first time our computing professor showed this in C literally heaven's door opened for me lol It was magical and it has helped me so many times through the years, writing regular expression parsers at work, simplifying state machines, even in the Advent of Code competence I've solved several problems by building a state machine (like one for a "sokoban"-similar situation). 8:13 Python indentation 🤦‍♂

Studying formal language theory right now in undergrad to prepare for compiler theory. It's a fun subject

as a fellow German, I always kind of hoped, if I'd tried just hard enough maybe some day it wouldn't be so obvious, where I am from... guess I can take that off my list of things ever to achieve.

Learning Automata next? Love seeing some computational theory. Makes me want to dust off my undergrad books. I guess if I wanted an automata review I could knock on my office neighbors door since he worked with Thathachar in the 80's, but there's just something about that Computerphile charm that's kept me hooked from undergrad to faculty :) (well, maybe just Numberphile at the start)

Currently working on a query language using NFAs. Funny to see this video pop up! Really enjoyable

Wow I never knew the train driver from Matrix was real

Python can use any Unicode symbols of a written language for variable names, that is to say in general symbols which represent "letters" (for some expanded definition of the term "letters"). Therefore if you use the actual Greek letters in Python, and not some mathematical specific versions of them, it is valid Python, e.g.: class Foo: def __init__(self, Δ): self.Δ = Δ

I love finite state automata! Excellent video. Prof Altenkirch is brilliant and perfectly fits comp sci professor archetype.

Dammn we missed this man

How do these videos always get timed so we'll? I'm literally working on a class project doing exactly this. With the addition of providing a GUI representation for the FA.

I remember doing my Automatentheorie class online and it was somewhat troublesome. But across a few other classes, I got most fundamentals of formal languages. It does help to have seen most of this, now where I actually get to use lexers and tree parsers etc. I was close to writing a term paper on subsets of DFAs (or even PDA) for example those you can minimize, those with exactly one state, those in some normal form etc. But bailed on that eventually.

very much interested sir. superb explanation

"b", "bbbb", etc. would also return true. I.e. it doesn't satisfy L={words where as come before bs}. It's more like L={words where 'a's don't come after 'b's}

nice intro to tokens at the beginning. I'll use that, thanks

Finally a computerphile video I can get my hands in!! Your implementation is nice from a pedagogical perspective. No complaints. But I would like to give a more mathematical perspective. Without initial and final states, automata are the same as "transformation semigroups" that are a generalisation,so to say,of permutation groups. So the only thing you need to encode are the letters as functions from Q to Q, the set of states. If you give to each state a natural number (beginning with 0) a function can be encoded in a list F, where F(i) is just the element in the position i of the list. A little word can allow you to compose functions F and G. And voilà! An automaton is just a list of same length lists. Do you want to recognise languages? No problem. Specify the index of q0 and the set of final states and after applying the word (composing the functions) you check if position q0 is in the final states set. Easy and fast. Sorry for 1. The long answer just talking about something tangential to the video. 2. If you knew this. 3. If I didn't explain myself well enough. I hope to all computer scientists who are interested in automata and don't know about semigroups that they find a lot of answers on that wild untamed territory.

One of his students being taught the module hes literally describing. Very good content if you want to learn how compilers and programming languages work

I learned about this in my last week of discrete structures of math class for computer science. I wish I had seen this video earlier

I like the implementation as a dictionary, makes it very easy to generate new state machines

3 weeks into my automata theory course and i understand nothing. This video was elixir for me.

🎉 reminds me of my CS course unit over 8 years ago😊

I enjoyed learning this method much more with a mathematical approach instead of arbitrary languages. The easy one being whether or not a binary number was even. The initial state of 0 was the final state. The input sent to the matching state (so a 0 would send it to state 0, no matter which state it was in, and 1 sent it to state 1, no matter which state it was in).

Wasn't expecting it to cut there. It's like we spent this time defining something, and then didn't do anything with it...

But what's use of automata, especially in engineering problems?

I clicked on this video so hard I think I broke my mouse.

What’re the practical usages of a DFA beyond compiling - are there any?

What is that paper called??

is this Trainman from the matrix?

if q == 2, it's not in self.F, does that output False?

I'm taking this class right now and I have my first test in two weeks. I'm scaring of failing. My professor is a very though grader. Any tips on how to prepare as best as I can?

Question, if the rule is "words where As come before Bs", how can epsilon (empty word) be ok? There's neither an A nor any B so it doesn't satisfy the rule. Not?

Why not defining the final state, as „own state“ in the graph? I.e., arrow to state 3; end. Also why not stop immediately when reaching state 2, the invalid state?

Hi, guys! Thanks a lot for the content you are producing. Can you, please, help us understand how Fast-Flux works? I saw the video explanation of this concept is scarce, it might be an interesting security topic. :)

is this an automaton in the sense that it's a set of rules that determine the "evolution" of whether a word is or is not valid? i'm only used to seeing cellular automata like conway's game of life

Instead of the while loop in the run function, it would be better to just loop over each symbol with a simple for loop. Then, w = w[1:] would not be needed anymore (does an unnecessary copy).

When I saw Automata I thought of the games for the Sinclair computers - including PIMania.

That's one really strange way to iterate over the string 😕Why constantly truncate the string and get its 0'th element? Much better and cleaner is: ....for letter in w: ........q = self.delta[(q, letter)]

A perfect opportunity to use list comprehension instead of a loop

What is the difference between a sequence and a set? Why was a set of chars an incorrect answer to what is a word?

Type hinting would be nice e.g. def my_function(my_string:str) -> str: return my_string

A word is a set of characters … if you’re dyslexic

Nice!

Write a code that accept all such video which contains implementation of automaton in python.

На 8ой минуте на экране представлен перебор символов строки в цикле, почему он так реализован?

yo. wow. I think i know where to start to make my own language and complier now. obv i have a long way to go bot wow this is so cool.

I think it's much clearer with these variable names. And there's a little less code with the dataclass: @dataclass class DFA: set_of_states: set set_of_symbols: set transition_map: dict initial_state: int set_of_final_states: set def run(self, symbols): current_state = self.initial_state while symbols != "": current_state = self.transition_map[ (current_state, symbols[0]) ] symbols = symbols[1:] return current_state in self.set_of_final_states

👍Thanks.

Thanks for the video. I'd have more explicitly stated the rules for the example dictionary; where -ALL- a's come before -ANY- b's. Otherwise, you could read it like so; where -SOME- a's come before b's, which renders aba a valid word.

👍

You see if we do some math, we need to have some Greek letters.

Errrr what about ‘bbbb’?

Did I learn anything? No. Did I like his accent? Yes

Hey, it’s the train man!

why not Σ instead of sigma?

Just started that chapter in the dragon book. Must be a sign

Professor Thorsten Altenkirch looks like if Dave Grohl and Taylor Hawkins were 1 person and playing in a band called Foo(x) Pythons.

You should be in james bond movie

4:59

I’m thinking about making a similar video but about famous hacks in documentary format

What no 'bb' ? 😢

You can just use "for c in w" instead of a while loop. Also, you don't need to compare with an empty string - "while w:" does the same thing.

Hi

This probably makes it a lot less dry for people who dislike math.

Scary

damn i like this channel videos but i hate the sound of that pen writing on this paper idk why but cant resist it

Silly 😅 how calls an alphabet (αβ) Sigma Σ?

It’s like he’s trying to speak without moving his mouth

Noice

Would "abb" fail? It seems like it should pass.

Why have "sigma" in "init"? Is it ever used in the implementation?

Can someone have more "Rick" vibes than Thorsten? :D

love me some fellow Germans that are unconventional :)

nice vid, but my inner pep-8 cries

Excellent video, I didn't think impenting an automaton would be so easy. MacOS tho ewwww

"I did something wrong ... Oh ... I set my indentation levels wrong" That's why I use javascript over python every time.

6:00 Please tell this learned professor that PEP-8 is a thing; spaces after commas. Computer languages are a standard, only some of those standards are enforced by the compiler but we're still subject to them because they're a good thing. Also, come on, this is too simple to justify complicated words. Also also, to anyone that has had to write complicated regex expressions and refused to learn any more than they needed for the exact use case, I feel you.

I love computerphile but would appreciate if the videos would be more concise. Also the code is very verbose. I would appreciate something like def run(state, delta, final, word): while word: symbol, *word = word state = delta[(state, symbol)] return state in final delta = {(0,"a"):0, (1, "a"):2, (2,"a"):2, (0,"b"):1, (1, "b"):1, (2, "b"):2 } run(0, delta, (0,1), "aab")

I love this guy but the lack of pep8 drives me nuts.

This video is a little underwhelming. Not gonna lie.

Only problem with this channel is the atrocious act of using a marker on paper.

Is this the train guy from matrix 3