topic: Intro to Finite State Machines
So far we have discussed two concepts. Those include Turing machines and Regular expressions. In the upcoming articles, we're going to extend our intuition on these two concepts and merge them. Before that, let's jump start with a new terminology - Finite State Machine.
What is a Finite State Machine? #
A finite state machine is a conceptual model of computation. Which always possess a specific state chosen from a finite set of possibilities. The machine is able to transition between states based on some inputs. Finite State Machine is an abstract idea, which expresses some computational logic as state transitions. Its implementation can vary based on the requirement. If you recall correctly, you will understand the fact that Turing Machine is a specific kind which is a low-level implementation of State Machine. What more interesting is, the concept of State Machine can be applied at multiple levels of abstraction within a single system. We will see some examples in this and the upcoming articles.
Logic representation in a Finite State Machine: #
As we have mentioned above, any machine should settle in a state at any time. At the very high-level, the machine state can be a 'running' or a 'stop' state. Suppose our example machine is currently in its 'stop' state. If we give it an input say 'ON', the example machine will transition from 'stop' state to 'running' state. When 'OFF' input is given, the transition will happen from 'running' to 'stop' state.
Maybe we could use another low-level State Machine to further deduce the 'running' state. We can follow the same deduction process and move to the very low-level abstractions. By doing so, we might end up in something similar to a Turing Machine. That makes sense. right?
Let's combine what we have learned so far: #
In the first three articles in this blog series, we have discussed what a Turing Machine is and built one. And from the above examples, it became more clear to us that, Turing Machine is a specific State Machine and paves the foundation for any complex computations to be developed upon it. Also, we have seen that we could deduce any logical problem into a State Machine model.
In the second three articles, we have learned what Regular Expressions are and how they could be used to perform two basic NLP problems - classification and entity recognition. We also have created a clone of rule-based ELIZA chatbot based on this idea. What if I say, Regular Expressions make use of State Machines to recognize patterns in an input sequence? Yeah! it does. In the next article, we will focus more on this and will see examples.
Contexts and chatbots: #
To build our first chatbot, we used text classification and entity recognition to understand user utterances. But that's not enough. Context awareness is another important feature that our bot needs. There are different techniques that we could use to achieve this. In my opinion, keeping track of states and transitions between different states is enough to give better intelligence to a memoryless bot. Game developers use this technique to implement a handful of things including parts of AI in games (I found it great and flexible when I had a lot of time to waste and make some tiny games, miss those days..). We will discuss it in the third article in this session. We will also create a simple bot on that day. So until then.., see ya.