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
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.
+Bob Lake But originally, in older vending machines, etc.- the "state" would just be the current configuration of all of the levers, toggles, et al, that have been changed due to the different types of coins being dropped in.
+Amr ElAdawy Well around here parking meters might give you as much as an hour per quarter ($.25), but they don't print tickets (obviously; they're meters). You'll only get a ticket when paying to park in a lot or garage, which is much more expensive. Badly maintained parks on the fringes of the city might only charge $3/hr, but generally you're looking at $5-25 for the first hour. In Chicago and New York, it can easily be twice that.
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.
+I'm Very Angry It's Not Butter You're thinking too much about the actual implementation and that's not really the point here. You would just add those states to the diagram and named the transitions like -5, -10. The fact that the machine is unable to return 10p coin is irrelevant in this case.
Actually you don't even need the 25 state. You can make the output not only depend on the state but also on the input. If the state is 20 and you add 10p, just add logic that says 20 and 10p - - > print ticket, return 5p, state 0
***** I don't think the machine requires any memory to know what coins are available to dispense. Separating the coins does not require a computer; it can be done entirely mechanically. Vending machines have had such non-computerized systems for decades. The machine does not need to keep track of the exact number of coins in each chamber; it just needs to know whether each chamber is "empty" or "not empty". To that end, a non-computerized hanging scale is attached to each chamber. If the chamber is at its default weight (i.e. empty), then the levers within the scale complete a circuit which sends an electric signal indicating that the chamber is empty. However, if the chamber is any heavier than its default weight (i.e. it contains coins), the circuit is broken, and there is no electric signal.
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.
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 :)
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
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.
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.
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.
You're not saying anything new. He never said that it isn't memory, but rather that devices with this ability don't need (to *have* ) memory (because they *are* memory). TO HAVE != TO BE. Memory doesn't need memory; it's already it. E.g. a simple computer code parser as he described doesn't need a variable to store the parser's state: the parser, just, *is* in some state. A coupla _while_ and _if then else_ arrows is all that such a parser needs to be in this or that state.
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.
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).
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.
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.
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.
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.
Felds Liscia Haha, that's amazingly awful. It looks like anything that PHP can coerce to any string works. ${""}, ${[3]}, ${new SplTempFileObject()}, knock yourself out! :D This language never fails to surprise me.
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.
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!!
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.
@@yuzan3607they mean a syntax parser can be modelled as a finite state machine. The state machine reads all characters from the syntax input in order. Each character triggers a state transition. If the machine reaches the final state, the syntax is valid, otherwise it's not.
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.
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.
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
jakejakeboom Huh. I don't remember discussing FSAs in my embedded systems course...but that was only one semester years ago, so I could have just forgotten XD
+IceMetalPunk in embedded control engineering we just call them state machines. Very simple to define complex behaviour which is fast to implement and easy to get right with predictable behaviour. Gives you a lot of performance with little risk of bugs. And starting with a state diagram like that shown means it's easy to get your head around the function and make changes when needed.
Are they useful for computer scientists? meaning did you use them in your job? It'd be ironic if you've never had to use them, and me an engineer who knows nothing about all of this am back to learning them because I need them in my job.
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.
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 UA-cam , but I love watching Computerphile videos.
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 :)
The state machine is wrong, you should make states which will result in the machine giving change... For example you can give 3 "10p" coins and en up with 30p and the machine in this state will give you 5 p change and go to finish state. This is really basic...
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.
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.
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
About introducing a 25p coin. I remember spending two weeks in London a couple of years ago and I just found the coin-system bewildering. 1p, 2p, 5p, 10p... pretty soon I had a wallet filled up with 20 different kinds of coins (that's what it felt like at least) that I had to scrutinize and tally up to buy a mars-bar when I'm in a shop with 5 people behind me. The result? "Bugger this! Keep the change". This is me coming from a country that at the time had 3 kinds of coins. 1, 5 and 10 SEK. We had "öre" too that was 1/100th of a SEK. But we got rid of them because of the inflation they were basically worthless anyway. And it practcally works without fail. So my advice is to not introduce more denominations. Instead, simplify... 10p, 50p and 1£... do you loose some pennies due to rounding up and down? Yes. But just think of all the time and space wasted in general fiddling about with coins that aren't' worth the metal its minted on. The US system is just barely better at this. But even their smallest cents are worthless. I'd be perfectly happy if the quarter was the smallest one... or we can all just stop this nonsense and do away with cash alltogether. ok. Rant done... Interesting video by the way. I really like this channel. :)
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 don't think it would have helped. literally implementing the diagram would produce incomprehensible code, that would require this diagram to understand
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?
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...
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.
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?
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.
So an if-then-else statement that sets a boolean variable to either true or false according to certain conditions determined by the if-then-else statement is basically a finite state automaton?
coldlettersofficial So has anyone ever tried to (theoretically) build a Touring-complete machine out of finite-state-automata, or is this mathematically impossible? Maybe plus some memory, if that is necessary for a machine to be Touring-complete.
+Seegal Galguntijak Turing completeness requires memory; in Turing's classic model, there's a tape that stores symbols. Once you add memory, it's no longer a finite state automaton.
Seegal Galguntijak well the problem is that a Turing-complete machine is a Turing machine which needs RAM. But a Finite state machine has no Ram, Stack or sth like that. So what we need is a Infinite state Machine (but that is a turing machine). In short: No A finite state machine can never be turing complete
coldlettersofficial I see, so mathematically, only an infinte number of finite state machines could be Turing complete. Interesting, thanks for the explanation, also @ IceMetalPunk
I don't understand. The FSA has a memory of one word, in this case up to 25 and worth say, 5 bits. What if its "single word" of memory was worth a trillion bits? And, it had a ridiculously large but technically finite graph of all the operations it could perform on that single word (or number) composed of a trillion bits? (In other words, couldn't you create a Turing complete machine with an absurdly complicated FSA?) As an example, he says you can't have the machine remember which coins led to 15, but adding a few bits to the number you could store that using a bit of math (mangling the number but it would still be extractable by a simple modulo).
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
false.
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
+Charmonium Pentaquark I wish I had that shirt. :(
Supplied by Peleg Bar Sapir (see description), apparently
ok?
Am I the only one really annoyed that there isn't a 20p going from 5 to 25? >:(
ikr
No your not ...
+Robert Smith
Ja, da fehlt ein 20er-Bogen von 5 zu 25.
+Robert Smith I had this same thought. :-|
+Robert Smith me too ^^
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.
+Bob Lake But originally, in older vending machines, etc.- the "state" would just be the current configuration of all of the levers, toggles, et al, that have been changed due to the different types of coins being dropped in.
??
This man really know how to explain stuff :D
+Ameer Fazal He's an ancient geek
He was at the battle of Troy
long before SQL injection
+Omar Omokhodion He collaborated with Archimedes, on building the first computer XD
+Omar Omokhodion Don't you mean "Greek Injection" (via the wooden horse)
+tscoffey1 Actually it's not an injection because it required installing a Trojan horse.
7 years later this man, is still, improving students' lives, really thanks
??
2 hours of parktime for 25p? Is this real?
+Дмитрий Корьяс Maybe in 1970 lol.
+Дмитрий Корьяс Areas of Nottingham have 2 hours free for most(all?) car parks.
+Дмитрий Корьяс The number was picked purely because it was small enough to not be long, but still enough to be complicated.
+Дмитрий Корьяс We pay almost 38P for one hour only !!!
And sometimes 58 for one hour.
+Amr ElAdawy Well around here parking meters might give you as much as an hour per quarter ($.25), but they don't print tickets (obviously; they're meters). You'll only get a ticket when paying to park in a lot or garage, which is much more expensive. Badly maintained parks on the fringes of the city might only charge $3/hr, but generally you're looking at $5-25 for the first hour. In Chicago and New York, it can easily be twice that.
This is actually a really great introduction to automata and formal languages, great examples.
false.
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.
+I'm Very Angry It's Not Butter You're thinking too much about the actual implementation and that's not really the point here. You would just add those states to the diagram and named the transitions like -5, -10. The fact that the machine is unable to return 10p coin is irrelevant in this case.
+I'm Very Angry It's Not Butter Simple and effective. Nice one!
Actually you don't even need the 25 state. You can make the output not only depend on the state but also on the input. If the state is 20 and you add 10p, just add logic that says 20 and 10p - - > print ticket, return 5p, state 0
+TribeWars1 but it doesn't know the previous state. unless you mean it checks the state and value of the coin coming in.
*****
I don't think the machine requires any memory to know what coins are available to dispense.
Separating the coins does not require a computer; it can be done entirely mechanically. Vending machines have had such non-computerized systems for decades.
The machine does not need to keep track of the exact number of coins in each chamber; it just needs to know whether each chamber is "empty" or "not empty". To that end, a non-computerized hanging scale is attached to each chamber. If the chamber is at its default weight (i.e. empty), then the levers within the scale complete a circuit which sends an electric signal indicating that the chamber is empty. However, if the chamber is any heavier than its default weight (i.e. it contains coins), the circuit is broken, and there is no electric signal.
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.
??
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 :)
this is the knowledge I been waiting to learn im finally satisfied with this explanation thank you
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
Memoryless is a technical term. It means that the next state only depends on the current state. See “memorylessness” on Wikipedia.
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.
ok?
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.
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.
Having the ability to store a state, *is* memory, whether that state is stored mechanically or electronically.
You're not saying anything new. He never said that it isn't memory, but rather that devices with this ability don't need (to *have* ) memory (because they *are* memory). TO HAVE != TO BE. Memory doesn't need memory; it's already it. E.g. a simple computer code parser as he described doesn't need a variable to store the parser's state: the parser, just, *is* in some state. A coupla _while_ and _if then else_ arrows is all that such a parser needs to be in this or that state.
@@dariokartal9453 That's... a bit of a stretch.
??
6:54 COBOL allows for variables starting with a digit. That was very handy before the language got more structured features.
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.
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).
I always enjoy the videos with Professor Brailsford. This one is no exception. Thanks very much!
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.
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.
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.
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.
So technically you are not using a actual PHP interpreter/compiler/repl/whatever-it-is :D But I've heared people say GCC isn't a C compiler either.
So technically you are not using a actual PHP interpreter/compiler/repl/whatever-it-is :D But I've heard people say GCC isn't a C compiler either.
So technically you are not using a actual PHP interpreter/compiler/repl/whatever-it-is :D But I've heard people say GCC isn't a C compiler either.
+Schindlabua ${"💩"} works to. with that notation, the variables can be anything!
Felds Liscia Haha, that's amazingly awful. It looks like anything that PHP can coerce to any string works. ${""}, ${[3]}, ${new SplTempFileObject()}, knock yourself out! :D
This language never fails to surprise me.
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.
I don't know what it is, but there's something i love between the way he describes things and his voice :D
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!!
+Allan C-B History sure does repeat itself doesn't it?
Noah Williams Absolutely ! Though ... vending machines were around before IBM's PS/2 LoL
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.
I love this guy. I could listen to him for hours.
Finite State Automata = Regular Expressions
The base for syntax parsing in programming languages.
Alan Turing was a master in that field.
I don't know if you're still here (after 5 years), but can you explain exactly how syntax parsing is a finite state automata? I'm interested in that.
@@yuzan3607they mean a syntax parser can be modelled as a finite state machine.
The state machine reads all characters from the syntax input in order. Each character triggers a state transition. If the machine reaches the final state, the syntax is valid, otherwise it's not.
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.
If a parking machine can't handle overpaying, would you call it a parker machine? Oh, wait, wrong channel.
Pedro Paletta It's never the wrong channel. :D
??
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!
Modular synthesisers might be an interesting topic for a future computerphile video since they're actually special purpose analogue computers.
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.
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
embedded systems, hardware VHDL design... even in computer/electrical engineering
jakejakeboom
Huh. I don't remember discussing FSAs in my embedded systems course...but that was only one semester years ago, so I could have just forgotten XD
+IceMetalPunk in embedded control engineering we just call them state machines. Very simple to define complex behaviour which is fast to implement and easy to get right with predictable behaviour. Gives you a lot of performance with little risk of bugs. And starting with a state diagram like that shown means it's easy to get your head around the function and make changes when needed.
+IceMetalPunk If i remember correctly, the control unit of a MIPS multicycle is modeled as a state machine.
Are they useful for computer scientists? meaning did you use them in your job?
It'd be ironic if you've never had to use them, and me an engineer who knows nothing about all of this am back to learning them because I need them in my job.
I can listen to this man and Tom Scott all day and not get bored
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.
This guy makes paying a machine sound like a jolly walk in the park during an adorable day.
I would so much like to work with finite state machines and epsilon transitions, the graphs are just so beautiful.
Ay ay ay COMBINATORICS. I feel like this guy must be a terrific professor
??
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 UA-cam , but I love watching Computerphile videos.
This man was all over the place with his explanations
Very well explained, thank you
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 :)
Perfect timing! I'm just learning about these in one of my classes.
Live British coins! SO much more exciting that the caught and stuffed variety.
??
They made the T-Shirt! Is this the first video where that shows up? Behind on a few episodes...
The state machine is wrong, you should make states which will result in the machine giving change... For example you can give 3 "10p" coins and en up with 30p and the machine in this state will give you 5 p change and go to finish state.
This is really basic...
I love videos with this guy. He's enthusiastic and explains well.
Great series, I have learned a lot watching these videos
At the time this video was released we started the very same topic in the 12th class informatics course at my school.
The language that is taken as an example has one missing transition which is (5,10)-->25
@ 0:43 what is that 'f' doing there in the binairy code? (3rd row from the bottom, in the middle)
Isn't knowing what state the machine is in a type of memory? Or is the definition of memory more restrictive than that?
I was wondering the same. I think he didn't mean memory as RAM, but mamory as in recollection how you reached the state.
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.
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.
Are parking meters more common in the UK than in the States? I've only seen one parking meter in my life.
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
You should do something on lisps.
I haven't seen a Computerphile video on pushdown automata. Do you take requests?
I love when this Sir speaks he breaks it down to the lowest level...
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.
+Jackalope See the 'why binary' video... >Sean
About introducing a 25p coin.
I remember spending two weeks in London a couple of years ago and I just found the coin-system bewildering. 1p, 2p, 5p, 10p... pretty soon I had a wallet filled up with 20 different kinds of coins (that's what it felt like at least) that I had to scrutinize and tally up to buy a mars-bar when I'm in a shop with 5 people behind me. The result? "Bugger this! Keep the change".
This is me coming from a country that at the time had 3 kinds of coins. 1, 5 and 10 SEK. We had "öre" too that was 1/100th of a SEK. But we got rid of them because of the inflation they were basically worthless anyway. And it practcally works without fail.
So my advice is to not introduce more denominations. Instead, simplify... 10p, 50p and 1£... do you loose some pennies due to rounding up and down? Yes. But just think of all the time and space wasted in general fiddling about with coins that aren't' worth the metal its minted on.
The US system is just barely better at this. But even their smallest cents are worthless. I'd be perfectly happy if the quarter was the smallest one...
or we can all just stop this nonsense and do away with cash alltogether.
ok. Rant done...
Interesting video by the way. I really like this channel. :)
+jmalmsten It's really not that difficult to understand, but then I am a native, so I've been brought up with the coin values.
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 don't think it would have helped. literally implementing the diagram would produce incomprehensible code, that would require this diagram to understand
great great explanation
The diagram is missing the 5p and then 20p combination.
I want to know who eats a -bar- of chewing gum lol.
Do they really say Pee instead of pence in UK?
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.
If I remember correctly, traffic light controllers are also finite state machines.
Professor Brailsford you are the best!
So can we expect a video on Regular Expressions soon?
25p for 2 hours parking? Pffft.
On car parks owned by the roads department.
+James Gould **Steals your UA-cam profile picture**
??
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
hahah I just read the header and yes its true ;)
Only 2 days back I wrote that data structure mumbo jumbo for exam without understanding it's practical application. Now I get it! :-|
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?
Wonderful, clear explanation
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.
Where is this parking machine? I was out with a friend the other day, two hours cost £3.50! 😐
It's in the 70s I guess 😅
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...
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.
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?
Bringing back good memories of when I was in university.
128 valid combos?
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.
Is this actually how old vending machines work though? Like is there some physical analog for these states? It feels like an elaborate analogy to me.
So an if-then-else statement that sets a boolean variable to either true or false according to certain conditions determined by the if-then-else statement is basically a finite state automaton?
+Seegal Galguntijak yes! if the bool refers to the state. as long as your program does not know its "history", its always a finite state machine
coldlettersofficial So has anyone ever tried to (theoretically) build a Touring-complete machine out of finite-state-automata, or is this mathematically impossible? Maybe plus some memory, if that is necessary for a machine to be Touring-complete.
+Seegal Galguntijak Turing completeness requires memory; in Turing's classic model, there's a tape that stores symbols. Once you add memory, it's no longer a finite state automaton.
Seegal Galguntijak well the problem is that a Turing-complete machine is a Turing machine which needs RAM. But a Finite state machine has no Ram, Stack or sth like that. So what we need is a Infinite state Machine (but that is a turing machine). In short: No A finite state machine can never be turing complete
coldlettersofficial I see, so mathematically, only an infinte number of finite state machines could be Turing complete. Interesting, thanks for the explanation, also @ IceMetalPunk
I don't understand. The FSA has a memory of one word, in this case up to 25 and worth say, 5 bits. What if its "single word" of memory was worth a trillion bits? And, it had a ridiculously large but technically finite graph of all the operations it could perform on that single word (or number) composed of a trillion bits? (In other words, couldn't you create a Turing complete machine with an absurdly complicated FSA?)
As an example, he says you can't have the machine remember which coins led to 15, but adding a few bits to the number you could store that using a bit of math (mangling the number but it would still be extractable by a simple modulo).
Prof, when in the history of decimal currency did 25p get you 2h parking?
Would an old Otis lift with relay logic and awesome floor selector have memory?
Hi. Where does it store the current sum? Register is a short term memory?
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.
Pretty good dissertation on simplicity.
Can you please also make video on how programming language talk to processor
he talks about a computer without memory but presents a machine with state
I’m trying to figure out where in the world I can buy anything out of a vending (or park my car) for less than $1USD 0:50
To deal with overpayment, when there is an illegal coin if it isn't 1p or 2p you could just print.