Theory of computation (TOC) is one of the most important concept in computer science. It lays a strong foundation for abstract areas in computer science and teaches you about the elementary ways in which a computer can be made to think.
The finite-state machine is a branch of TOC. It is a mathematical model of computation or an abstract machine that can be in exactly one of a finite number of states at any given time.
They change states according to the given input. And at one time they are in only one state. One interesting fact is that they don't have any memory like RAM, ROM and do not store any previous information other than the state they are in. Still they do the processing.
The use of FSMs can be observed in many devices in the modern world that perform a predetermined sequence of tasks depending on the sequence of input provided. Examples are vending machines, which dispense products when the proper combination of coins is deposited, elevators, whose sequence of stops is determined by the floors requested by riders, traffic lights, which change sequence when cars are waiting, and combination locks, which require the input of combination numbers in the proper order.
Now let’s look at how earlier mechanical device i.e. A Parking lot Machine used FSMs for processing.
The machine is based on the principle of FSM. It accepts only three coins 5, 10 and 20. They are the inputs to the FSM. The machine has six states. When the user puts coins worth 25 units the machine prints a receipt.
The Finite State Automata is shown below.
As we can see the states of the machines are {0, 5, 10, 15, 20, and 25}. Initially it is at zero, when it reaches to 25 it outputs a receipt to the user.
The combinations of the coins that it accepts are:
That’s how they were use in the earlier Mechanical devices. But why do we still study them now as electronic microchips do the same job? Particularly, why do we study them as a part of computer science?
All machines/systems can be generalized as a FSM. Every system in computer science works in a same way. It receives some input, does the processing and gives output.
After each processing the system goes into another state, same state with loop or maybe final state.
Now let’s look at its very common application in Computer Science, a comment filtering system. Every programming language has comments. They are very useful at the time of coding but they aren’t compiled to the final binary code. So the system has to perform some filtering during compilation. FSM of such a system is given below. It filters the comments in a C/C++ code.
The format of comments in C and C++ are:
C: /* some comment here… */
C++: // some comment here
The above given FSM is embedded at a particular location in the compiler to escape the comments. According to the inputs (‘/’, ‘*’, ‘end-of-line) it moves to another state. When characters of the comments are found the state goes on a loop until it ends. Finally the control of the system returns to the ‘none’ state.
Another common example is the validation of variables/identifiers in programming language. An identifier consists of a combination of symbols, numbers and alphabets.
Some of the valid identifiers are:
A FSM can be constructed with certain restrictions to filter invalid identifiers. Not only identifiers, it can be used for any other string matching operations too.
As we have seen, they are useful it a lot of ways and serve as a basic model of computation in computer science. They are also used in games for AI, implementations of user input handling, navigating menu screens, and parsing text and network protocols.
References:
https://www.ics.uci.edu/~eppstein/161/960222.html
https://en.wikipedia.org/wiki/Finite-state_machine
https://www.youtube.com/watch?v=vhiiia1_hC4
The finite-state machine is a branch of TOC. It is a mathematical model of computation or an abstract machine that can be in exactly one of a finite number of states at any given time.
They change states according to the given input. And at one time they are in only one state. One interesting fact is that they don't have any memory like RAM, ROM and do not store any previous information other than the state they are in. Still they do the processing.
The use of FSMs can be observed in many devices in the modern world that perform a predetermined sequence of tasks depending on the sequence of input provided. Examples are vending machines, which dispense products when the proper combination of coins is deposited, elevators, whose sequence of stops is determined by the floors requested by riders, traffic lights, which change sequence when cars are waiting, and combination locks, which require the input of combination numbers in the proper order.
Now let’s look at how earlier mechanical device i.e. A Parking lot Machine used FSMs for processing.
The parking lot machine
The Finite State Automata is shown below.
As we can see the states of the machines are {0, 5, 10, 15, 20, and 25}. Initially it is at zero, when it reaches to 25 it outputs a receipt to the user.
The combinations of the coins that it accepts are:
- 5, 5, 5, 5, 5
- 20, 5
- 10, 10, 5
- 5, 5, 10, 10, 5 etc.
That’s how they were use in the earlier Mechanical devices. But why do we still study them now as electronic microchips do the same job? Particularly, why do we study them as a part of computer science?
FSM in Computer Science
After each processing the system goes into another state, same state with loop or maybe final state.
Now let’s look at its very common application in Computer Science, a comment filtering system. Every programming language has comments. They are very useful at the time of coding but they aren’t compiled to the final binary code. So the system has to perform some filtering during compilation. FSM of such a system is given below. It filters the comments in a C/C++ code.
The format of comments in C and C++ are:
C: /* some comment here… */
C++: // some comment here
The above given FSM is embedded at a particular location in the compiler to escape the comments. According to the inputs (‘/’, ‘*’, ‘end-of-line) it moves to another state. When characters of the comments are found the state goes on a loop until it ends. Finally the control of the system returns to the ‘none’ state.
Another common example is the validation of variables/identifiers in programming language. An identifier consists of a combination of symbols, numbers and alphabets.
Some of the valid identifiers are:
- hello;
- hello123;
- hello_123;
- 123hello; //identifiers cannot start with numbers
- 123@34; // @ symbol is invalid
A FSM can be constructed with certain restrictions to filter invalid identifiers. Not only identifiers, it can be used for any other string matching operations too.
As we have seen, they are useful it a lot of ways and serve as a basic model of computation in computer science. They are also used in games for AI, implementations of user input handling, navigating menu screens, and parsing text and network protocols.
References:
https://www.ics.uci.edu/~eppstein/161/960222.html
https://en.wikipedia.org/wiki/Finite-state_machine
https://www.youtube.com/watch?v=vhiiia1_hC4
0 comments:
Post a Comment