That guy was born to teach. He loves it, he has a nice slow rhythm in speaking, and enunciates the words at just the right time

I love how in one video he said "if someone wants to make a shirt with this equation on it, i would wear it" and now he is wearing the shirt with the equation on it XD

Am I the only one really annoyed that there isn't a 20p going from 5 to 25? >:(

7 years later this man, is still, improving students' lives, really thanks

This man really know how to explain stuff :D

Finite state machines are everywhere, from stand-alone applications, like this vending machine example, down to the internals of processors and other complex logic chips. The only "memory" they need is a register holding the current state. And that "register" can be implemented with multiplexers (in which the next state is dependent on the mux's current state [outputs] combined with inputs from the system being controlled, and pre-programed input values, determined at design time ), or logic gates that compute the next state on the fly.

I remember getting onto an elevator, with people in it already. I pressed the button for my floor and the guy already in the elevator said that it's a grandpa-elevator. This left me with a puzzled look on my face. The guy continued, "no memory". Meaning that the elevator would not remember me pressing that button and I'd need to press it again when it next stopped. And this happened in Finland where nobody does smalltalk.

2 hours of parktime for 25p? Is this real?

It would be so simple to make a machine that handles overpaying. Just add 3 extra states: 30, 35, 40. - If 30, it dispenses a 5p coin if available, and moves to the 25 state. - If 35, it checks the weight of the 10p coins storage. Not empty? Dispense 10p and move to the 25 state. Empty? Dispense 5p if available and move to the 30 state. - If 40, it dispenses a 5p coin if available, and moves to the 35 state. This way, it refunds exact change if possible; otherwise, it refunds as much as it can without going over.

Having the ability to store a state, *is* memory, whether that state is stored mechanically or electronically.

This is actually a really great introduction to automata and formal languages, great examples.

The very first component in a compiler is a lexical analyzer which is perhaps a fancy name for an implementation of a finite state automata. It receives a stream of characters (probably encoded in some form to save space and computation time for reasons I cannot immediately explain) and just by moving from one state to another it knows to detect the appropriate token. It also associates a token with a lexeme which is the value of a detected portion of the stream of characters (for example, if the token is a number, then its lexeme might be the value of the number). Those tokens are then parsed by a syntactic analyzer (or parser). The power in lexical analyzers as said in the video is that they don't use any extra memory and they go over their input exactly once (that is to say, the memory complexity of lexical analyzers is O(1) and the time complexity is O(n)). The way they can be implemented is as simple as a two dimensional array that with the indices of it being the characters themselves and a special flag for each input receiving state (unlike conventional FSAs, lexical analyzers can have more than a single type of input receiving state - each type of state corresponding to each type of token). I personally find the simplicity behind them and generally compiler front ends to be incredible. Compilers are made of components, each extremely efficient and incredibly simple for the job it is doing. Yet together they perform a very important and complex task.

Could you make a video about how people make programming languages, what kind of software is used to build them, etc?

I can listen to this man and Tom Scott all day and not get bored

Live British coins! SO much more exciting that the caught and stuffed variety.

I always enjoy the videos with Professor Brailsford. This one is no exception. Thanks very much!

Ay ay ay COMBINATORICS. I feel like this guy must be a terrific professor

I really enjoyed that. I learned all of that new and some of it wasn't able to sink in, but most of it really tickled the neurons, so thank you!

Perfect timing! I'm just learning about these in one of my classes.

Great series, I have learned a lot watching these videos

Thanks much for this video. I used a finite state machine when coding a library for sending SMTP mail back in 1994 -- it for an uncommon programming language. It sure made the coding very easy and you could visualize the code by looking at the graph. The graph was easy to draw because it made sense and the coding was like 15 minutes because I had the Finite State Machine. Thanks for refreshing my memory because I forgot how to even draw a finite state machine after not using htem for so many years :)

Fun fact: In PHP your variable names can consist of only numbers. $1 = "Hello World"; // Syntax error: Unexpected '1' (T_LNUMBER) yada yada ${1} = "Hello World"; // works just fine Which is funky, since in the PHP docs it explicitly says "A valid variable name starts with a letter or underscore, followed by any number of letters, numbers, or underscores". It seems like that rule is only enforced by the parser and can be circumvented easily anyway! PHP is also a big mess though, so stuff like that is to be expected.

I love videos with this guy. He's enthusiastic and explains well.

Thank you so much Professor Brailsford, I love this topic... And I have to admit, at least for me you Sir are the best at explaining something! The enthusiasm is intense, it's like a grandfather telling old stories near a campfire..I just love it.

Very well explained, thank you

I would so much like to work with finite state machines and epsilon transitions, the graphs are just so beautiful.

I don't know what it is, but there's something i love between the way he describes things and his voice :D

I love this guy. I could listen to him for hours.

This brings me back to my Models of Computation course days at uni...and my Foundations of Computer Science course...and my Programming Language Design course...actually, guys, these things are everywhere in computer science XD

If a parking machine can't handle overpaying, would you call it a parker machine? Oh, wait, wrong channel.

Every time I watch this I understand more and more. Like 5,5,5,5,5 is one of the acceptable strings/words in the Language of the machine i.e will allow the transition to the end state.

Wonderful, clear explanation

The great way about finite state machines, or about writing an arbitrary program as a finite state machine, is that if you have defined all the possible states and all the possible transitions the program can never find itself in an unexpected situation. Highly reliable programs can be made by thinking of the processes as finite state machines. The example is simplistic, but any program can be converted to a fsm. You can have any number of states, inputs, outputs, transitions and if you loop an output to input you can call it a variable.

6:54 COBOL allows for variables starting with a digit. That was very handy before the language got more structured features.

I didn't like the statement that the finite automata is a memory less system. I argue that the retention ability of the system to store the present state is itself a demonstration for the system to have a memory

What you spoke about, reminded me a LOT of the IBM PS/2 'terminals' I used in 1995(ish) at school. They had NO HDD's, and very very limited memory ... they were 'token ring' connected to "Enterprise" the schools mainframe. When I'd log in, I was logging into the mainframe, and the actual terminal was ... well like the "slim" terminals of today. My data was 'stored' (much like the cloud) on the mainframe server. IBM was ahead of the time with "slim terminals" and "cloud computing" I guess!!

Awesome video!

Modular synthesisers might be an interesting topic for a future computerphile video since they're actually special purpose analogue computers.

If I may add a little correction - in a typical DFA (Deterministic Finite Automaton) for a compiler's scanner module - the 'end of an identifier' is not limited to a ; or a , but more reasonably anything that is NOT allowed to be part of a variable name, so if a variable name consists of a starting letter and a any number of letters or digits (letter (letter | digit)* which read a letter followed by any number of (either a letter or a digit) ) [ this is called the equivalent Regular Expression] [ For each regular expression there exists a DFA and vice versa] then typically the 'end' is denoted by anything NOT a letter or a digit. so you would start in state 0 and to go to state 1 you need to see a letter, if you see anything else you go somewhere else (or error) in state 1 you keep recursing for as long as you see letters or digits and if you ever seen anything that is not a letter or a digit you go to state 2 and accept an identifier (without removing the last character you read as it will be needed in the next invocation of the machine).

No memory in principle but every State Machine implementation I've used (Harel State Machines usually) require lots of memory to handle transitions, guards, timers, the states themselves, entry/exit actions, etc. Qt, Rhapsody, QP, Sparx, etc. are all examples of useful state machines imps that require memory. This is the disconnect with the abstract field of CS and the people that actually do this stuff to make useful software.

Yes, the missing transition from 5 to 25 is the one that caused me a headache but i'll just call it a feature :D The speck in the eye of his neighbor see and log in ones not to notice.

Vending machines really have been around a long time: the first recorded one was built by Heron of Alexandria, who lived around 10-70 AD, and simply consisted of a machine with a coin slot that would dispense a fixed amount of holy water at a temple.

Pretty good dissertation on simplicity.

Professor Brailsford you are the best!

5:32 - I think that most machines, even in the early days, use the width of the coins. Think there is a couple of numberphile videos about this working towards solids of constant width.

Can I hope for a video on Banker's algorithm for deadlock avoidance while resource allocation by operating system. I know there are lot of videos on this here in UKposts , but I love watching Computerphile videos.

This man was all over the place with his explanations

Finite State Automata = Regular Expressions The base for syntax parsing in programming languages. Alan Turing was a master in that field.

Love the T-shirt Prof its awsome :).

great great explanation

Hey, if you're like me and like to write short programs in BATCH (which some could argue is not a programming language but I genuinely don't care), variables have to be surrounded by percent signs (%), meaning you can have any symbol or combination of symbols excluding the percent sign. This also means spaces, leading numbers, you can even name a number 999 should you want to, just by typing %999%. That's why I like using batch.

At the time this video was released we started the very same topic in the 12th class informatics course at my school.

Just to point out that a state machine like that is itself memory. It knows what state it is in and maintains that state until it gets a new valid input.

Depends on how you look it, those computers still have a memory, even if mechanical but they know how much money you put in. It does not know how did it get there or how much does it have totally but when the buyer begins putting in coins there is a temporary memory. Its really like a variable actually because a computer does not have to know anything other than numbers are adding up to it and at 25 (as an example) it will do something, then it will reset, regardless of what the result is. The other thing is, because you mentioned vending machines, either way you put it (mechanical or digital) the machine will get the message of what you want and will wait for the proper amount of money and will no what actions to perform so it can give away the following product. I'm probably complicating things but either way its still a form of memory whether or not it can be altered by the user or the device itself. The only thing with these is that this is rather a "mechanical approach"...?

The application to practical computer science is not checking variable names specifically. It’s REGULAR EXPRESSIONS in general. Every regular expression corresponds to a deterministic finite automoton.

a doubt, just trying to understand, we would still need memory to program the states right, like each state needs memory to know how to transition to a different state, and the transitions themselves would be volatile or temporary memory space which can even be constant, since all it needs to remember is the transition to increment the state, once the new state is reached, the current transition can be deleted or overwritten by new transition. if this is true, then the complexity of FSM specifically DFA should increase with the number of states to reach the final state, it will always be finite, but it is not constant and varies based on the problem, example if the parking ticket price is increased to 50p we would need more states to reach the final state. so we do need memory in the machine right, memory is required for one state to remember how to progress given a transition, and the point where memory is not required is that no state needs a history of how it has been reached, it still would need memory to know how to progress to the immediate next state so the machine should require memory. some of these might be very basic doubts, just want to learn and happy to be corrected :)

Hi. Where does it store the current sum? Register is a short term memory?

@ 0:43 what is that 'f' doing there in the binairy code? (3rd row from the bottom, in the middle)

25p for 2 hours parking? Pffft.

Are parking meters more common in the UK than in the States? I've only seen one parking meter in my life.

Would an old Otis lift with relay logic and awesome floor selector have memory?

I haven't seen a Computerphile video on pushdown automata. Do you take requests?

This guy makes paying a machine sound like a jolly walk in the park during an adorable day.

Surely the display of the amount entered so far is memory of sorts? It would be temporary memory that once the transaction is complete (I.E. the ticket printed) it gets cleared ready for the next coin to be inserted by the next customer. In programming terms it would be like a temporary variable in a function that is only used while that function is running.

In most cases, the parking meters here in sweden, will never reject a overpay. If you overpay, theres 2 possibility things that can happen: Either, it will do as nothing happened, eg it will allow you to pay for as much time as you want. HOWEVER, if you pay for lets say 4 hours on a 2-hour max park, then the person who are checking the parking spaces, will check the "issue time" on the tickets (valid from), and if that is more than 2 hour ago, then you will get a fine for overstaying. The second case with parking meters is that they are programmed with the max-stay time, but then, if you overpay, it will then "swallow" any overpay and then issue a ticket exactly valid for the permitted period. So for example, if a max 2-hour park costs 25 SEK for 2 hours, and you put in 3 pieces of 10 SEK equaling 30 SEK, then it will accept 30 SEK payment and print a ticket valid only for 2 hour. The ticket will instead adjust the price, so on the ticket, it will not say "12,50 SEK per hour" instead it says "15 SEK per hour", so all the number on the ticket match up.

Bringing back good memories of when I was in university.

I thought this was going to be about a computer I read about once (I can't remember where, or the computer's name) that had several hundred individual CPUs, each one connected to another 16 CPUs, and memory (other than, presumably, the registers in each CPU). The idea, apparently, was that the computer could, at any given time, hold all the information it needed to work with in the CPUs themselves, and had no need for system memory. I was curious to see if I would learn more about how that computer worked, and how successful the design was ultimately deemed to be.

awesome !

I love when this Sir speaks he breaks it down to the lowest level...

Only 2 days back I wrote that data structure mumbo jumbo for exam without understanding it's practical application. Now I get it! :-|

If I remember correctly, traffic light controllers are also finite state machines.

The language that is taken as an example has one missing transition which is (5,10)-->25

128 valid combos?

Isn't knowing what state the machine is in a type of memory? Or is the definition of memory more restrictive than that?

great communicator

for the simple example given here, the fsa approach seems more error-prone in design (he left a path out!) than just keeping a running total of value entered so far, which is childishly obvious. I can see the point for purely mechanical or similar implementation, but if we've got some silicon is there much point in this paradigm?

Where do you draw the line between "state" and "memory"? If an FSM can be in two possible states, is that not the same as one bit of memory? If you have a computer with 2GB of memory, is it not the same as an FSM with 2^(8*1024^3*2) possible states?

Can you please also make video on how programming language talk to processor

how about event system vs finate machine

I think there is mistake here, the vending machine has not temporary hosting, the coin dropa straight to the coin box. Thus register state is not applicable

I want to know who eats a -bar- of chewing gum lol.

So can we expect a video on Regular Expressions soon?

They made the T-Shirt! Is this the first video where that shows up? Behind on a few episodes...

In my language we actually call vending machines "automat" as well as the state machines. When I was telling people that I have exam from automata they instantly assumed I attend a course that's all about vending machines...

Prof, when in the history of decimal currency did 25p get you 2h parking?

You should do something on lisps.

We had to make a program in our C++ class that acted like a vending machine. I clearly wasn't that good as it confused the hell out of me. I got help from asking online; once I got pointed in the right direction I finally understood what do to. That was back in 1999. I think this diagram would be helpful.

I doubt variable names cannot start with a number for the convenience of the compiler. More likely, the rule is meant to improve code readability.

wont it need memory to store the current number?

The t-shirt, is that part of Graham's number? It would be nice to have a link to the full shirt since Professor Brailsford is wearing a jacket.

@Stephen Kamenar No it does not. It's an abstract concept and the example used im the video is only for easier explanation. Imagine a tree that has two states: "standing up" and "chopped down", then the transition between those states is simply chopping down the tree and because you can't really undo the transition, the second state is final (something that is a requirement for valid finite-state machine). Baaam, you have an example of finite-state machine that does not imply a memory in any way imaginable.

Why can not the programming lang be considered as some kind of memory?, per example: there should be a part that says "if it starts with a letter then its a variable", the lang itself is holding that information. Don't know about vending/parking machines though since i guess they don't use a programming lang.

He found the T-shirt he was looking for!

I use the vending machine in the reception of my apartment building for converting my 5p coins into coins that I can use in the washing machines, heh.

There are plenty of good applications for a finite state machine - but seriously this money counter isn't one of them! However, he's completely right about the computer language lexer - I've hand programmed several of these and they're great fun.

Holy crap I think that FSA is incomplete at there is a missing transition from s1 (5p state) to S5 (25p final state) as 5 + 20 = 25

K9 most awesome dog ever.

In Ottawa it's $2.00 for a half hour, but you had to park so far away it takes a half hour of walking to get where you wanted to go anyways.

Please let me know where I can park for 25p, for 2 hours.

Can you please tell me were I can get a bar of gum