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.
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.
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.
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.
+Massimiliano Tron Compiler theory is fairly complicated in general. However, there are tools that are used to generate compilers for simple languages - YACC (Yet Another Compiler-Compiler), and Lex (a tool that generates a lexical analyzer, which is what the professor was describing at the end).
+Massimiliano Tron The simplest technique is probably something called Recursive Descent. It only works with certain languages, but you can use it to hand build (without any tools other than a compiler and and editor) a parser for a fairly simple language such as Pascal. You can find lots of information about Recursive Descent on the web. Like all parsers, you need to start with the formal definition of the language, written in a formal language such as EBNF (which you should also be able to find on the web). Where it get really exciting is that EBNF itself is formally defined and pretty simple. So simple that you can easily write a parser for it, which outputs program source code to parse whatever language the EBNF is describing. This is one way that you can make a basic "compiler compiler".
+Massimiliano Tron You can use whatever existing language you like, the end result is machine code anyway. And that is what your language must be capable of becoming. Hard part ultimately is making a compiler that can translate reliably and quickly, that is where most if not all homebrew stuff fails.
+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.
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.
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.
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.
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
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 :)
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.
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.
@@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.
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.
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.
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!!
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.
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.
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).
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.
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.
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.
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.
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.
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 RUclips , but I love watching Computerphile videos.
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"...?
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...
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
Comment section should just accept that a state in a finite-state machine is not in fact a memory. The machine itself can't access any information about the state, it is just in a state in any given moment and can jump to another state if a particular condition is met. States are named (5, 10, 15, etc.) in the picture just for easier explanation. All of this is purely abstract and can't be mixed with electronics or mechanics. It's true that when you implement such abstract machine, you will probably use a some kind of memory, but that's completely irrelevant in the theory of finite-state 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.
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...
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. :)
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 :)
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
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.
Finite state machines are used all the time in programming. To, well, keep track of states. Not to mention regular expressions which I was a bit disappointed to learn this video didn't mention.
@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.
Everything in computing is ultimately a FSA, the processor itself is a FSA. This video is misleading as it implies that FSA are some obscure corner case rather than what they are, which is the fundamental concept from which all digital computers are built.
I don not quite agree... You will need more than 1 register... You need one register for the accumulator (sum of previous coins, the finite state) and also one register for the current coin being analyzed to be accepted/rejected... liked the video, thanks!
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.
Mechanical computers like vending machines and parking machines have a known state which is analogous to a register, just like the video says. But a register is technically memory.
ya know, the title is misleading. These computers, or state machines, rely on memory to function. it uses memory to remember the current state. Memory is a critical part of state machines.
He says the vending machine has no memory and doesn't need any, but that's not true. It has memory and uses it to keep track of what the total amount paid is. So it's one piece of memory that only stores the total amount paid thus far, but it's still memory.
Any actual computer with finite memory is a finite state machine. If we live in a finite universe, then all actual computers that will ever exist will be finite state machines.
In computer science “finite state machine” does not mean “a machine with a finite number of states”. It refers to a particular kind of machine called a DFA. DFAs can only accept or reject input (as seen in the video), while most computers can also write to memory... and then read in what they previously wrote. It is a much more expressive and dynamic process than what happens in DFAs. The theoretical model of computation that best corresponds to the machines we use in the real world is a finite Turing machine or “linear bounded automoton”.
Actually we did have 25 pence coins, but they were only issued as commemorative coins and have since been replaced with the £5 coin so it's understandable that car park ticket machines wouldn't accept them :)
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?
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
+Charmonium Pentaquark I wish I had that shirt. :(
Supplied by Peleg Bar Sapir (see description), apparently
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 ^^
7 years later this man, is still, improving students' lives, really thanks
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.
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.
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.
This is actually a really great introduction to automata and formal languages, great examples.
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.
Could you make a video about how people make programming languages, what kind of software is used to build them, etc?
+Massimiliano Tron Compiler theory is fairly complicated in general. However, there are tools that are used to generate compilers for simple languages - YACC (Yet Another Compiler-Compiler), and Lex (a tool that generates a lexical analyzer, which is what the professor was describing at the end).
+Massimiliano Tron The simplest technique is probably something called Recursive Descent. It only works with certain languages, but you can use it to hand build (without any tools other than a compiler and and editor) a parser for a fairly simple language such as Pascal. You can find lots of information about Recursive Descent on the web. Like all parsers, you need to start with the formal definition of the language, written in a formal language such as EBNF (which you should also be able to find on the web).
Where it get really exciting is that EBNF itself is formally defined and pretty simple. So simple that you can easily write a parser for it, which outputs program source code to parse whatever language the EBNF is describing. This is one way that you can make a basic "compiler compiler".
+Massimiliano Tron
You can use whatever existing language you like, the end result is machine code anyway. And that is what your language must be capable of becoming.
Hard part ultimately is making a compiler that can translate reliably and quickly, that is where most if not all homebrew stuff fails.
+Massimiliano Tron Send me a private message and if you like I can send you some chapters of a compiler construction book that I am writing ..
check out Forth, that's a language that can be implemented from scratch in a month.
I can listen to this man and Tom Scott all day and not get bored
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.
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.
Live British coins! SO much more exciting that the caught and stuffed variety.
Ay ay ay COMBINATORICS. I feel like this guy must be a terrific professor
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.
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.
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.
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 :)
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.
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.
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.
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.
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.
Very well explained, thank you
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
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.
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.
6:54 COBOL allows for variables starting with a digit. That was very handy before the language got more structured features.
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).
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.
this is the knowledge I been waiting to learn im finally satisfied with this explanation thank you
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
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.
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.
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.
25p for 2 hours parking? Pffft.
On car parks owned by the roads department.
+James Gould **Steals your RUclips profile picture**
I would so much like to work with finite state machines and epsilon transitions, the graphs are just so beautiful.
I love this guy. I could listen to him for hours.
I don't know what it is, but there's something i love between the way he describes things and his voice :D
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.
I always enjoy the videos with Professor Brailsford. This one is no exception. Thanks very much!
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!
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 RUclips , but I love watching Computerphile videos.
Storing a state isn't memory? WTF?
+
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"...?
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...
128 valid combos?
Perfect timing! I'm just learning about these in one of my classes.
Only 2 days back I wrote that data structure mumbo jumbo for exam without understanding it's practical application. Now I get it! :-|
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
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.
This man was all over the place with his explanations
The language that is taken as an example has one missing transition which is (5,10)-->25
At the time this video was released we started the very same topic in the 12th class informatics course at my school.
Comment section should just accept that a state in a finite-state machine is not in fact a memory. The machine itself can't access any information about the state, it is just in a state in any given moment and can jump to another state if a particular condition is met. States are named (5, 10, 15, etc.) in the picture just for easier explanation.
All of this is purely abstract and can't be mixed with electronics or mechanics. It's true that when you implement such abstract machine, you will probably use a some kind of memory, but that's completely irrelevant in the theory of finite-state machines.
They made the T-Shirt! Is this the first video where that shows up? Behind on a few episodes...
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.
This guy makes paying a machine sound like a jolly walk in the park during an adorable day.
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...
K9 most awesome dog ever.
+Jaime Cernuda Affirmative!
+Alex Trusk so did the BBC
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.
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 :)
Great series, I have learned a lot watching these videos
great great explanation
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 love videos with this guy. He's enthusiastic and explains well.
I love when this Sir speaks he breaks it down to the lowest level...
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 😅
If I remember correctly, traffic light controllers are also finite state machines.
You should do something on lisps.
Pretty good dissertation on simplicity.
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.
Finite state machines are used all the time in programming. To, well, keep track of states. Not to mention regular expressions which I was a bit disappointed to learn this video didn't mention.
+Penny Lane /regular\w+expres{2}ions?\w+(?:is|are)\w+fun/i
+Penny Lane He did a video about the Chomsky Hierarchy a week ago or so, I reckon regexes are coming :P
Schindlabua Quite possibly. He could have teased them though :)
@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.
Everything in computing is ultimately a FSA, the processor itself is a FSA. This video is misleading as it implies that FSA are some obscure corner case rather than what they are, which is the fundamental concept from which all digital computers are built.
I don not quite agree...
You will need more than 1 register...
You need one register for the accumulator (sum of previous coins, the finite state)
and also one register for the current coin being analyzed to be accepted/rejected...
liked the video, thanks!
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 doubt variable names cannot start with a number for the convenience of the compiler. More likely, the rule is meant to improve code readability.
Bringing back good memories of when I was in university.
Professor Brailsford you are the best!
Wonderful, clear explanation
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.
What a guy, makes we love computersience
Mechanical computers like vending machines and parking machines have a known state which is analogous to a register, just like the video says. But a register is technically memory.
ya know, the title is misleading. These computers, or state machines, rely on memory to function. it uses memory to remember the current state. Memory is a critical part of state machines.
The diagram is missing the 5p and then 20p combination.
He says the vending machine has no memory and doesn't need any, but that's not true. It has memory and uses it to keep track of what the total amount paid is. So it's one piece of memory that only stores the total amount paid thus far, but it's still memory.
It's a register which stores a pointer to the current state, not memory as in RAM.
when people say that their computer isn't confused, it isn't.
25p for 2 hours parking!? Where!?
Any actual computer with finite memory is a finite state machine. If we live in a finite universe, then all actual computers that will ever exist will be finite state machines.
In computer science “finite state machine” does not mean “a machine with a finite number of states”. It refers to a particular kind of machine called a DFA. DFAs can only accept or reject input (as seen in the video), while most computers can also write to memory... and then read in what they previously wrote. It is a much more expressive and dynamic process than what happens in DFAs.
The theoretical model of computation that best corresponds to the machines we use in the real world is a finite Turing machine or “linear bounded automoton”.
I want to know who eats a -bar- of chewing gum lol.
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 ;)
Awesome video!
Actually we did have 25 pence coins, but they were only issued as commemorative coins and have since been replaced with the £5 coin so it's understandable that car park ticket machines wouldn't accept them :)
Can you please also make video on how programming language talk to processor
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?
He found the T-shirt he was looking for!