Finite Automata

What is an Automata Anyway?

Automata some people call it automaton, is a mathematical model of checking if the input is valid or not valid as per our conditions. It is an abstract machine that takes inputs from a set of symbols or events and produces outputs by transitioning through a sequence of states based on those inputs.

Automata are used in a variety of fields, including computer science, electrical engineering, linguistics, and cognitive science. In computer science, automata theory is a fundamental concept in the study of formal languages, compilers, and software verification.

There are several types of automata. But, Noam Chomsky has classified into the following automata and respective grammar.

According to the above classification, we have 4 automata but, in this blog, we are just talking about finite automata.

Finite Automata

Finite automata is a type of automata in which we have less number of states. This automaton has very limited memory. This automaton can't help you with more complex problems. This automaton only accepts regular language. Below is a basic representation of how a finite state machine looks like:

We have three types of finite automata:

1. Deterministic Finite Automata (DFA),

2. Non-Deterministic Finite Automata (NFA) and

3. Epsilon-Non-Deterministic Finite Automata (ε-NFA)

1. Deterministic Finite Automata (DFA):

Deterministic Finite automata is formally defined as a 5 tuple machine M1,i.e.,

M1 = (Q, Σ, δ, q0, F)

Here, Every symbol in the definition is weird, below is the explanation of every symbol:

1. Q is the set of the states, as you can see in the below demonstration q0, q1, and q2 are the states of the machine. The Q set contains all of those states.

2. Σ is the set of input alphabet as you can see the alphabet 0 and 1 in the below example, that is being read by the machine. Those symbols are inputs and Σ is the set containing those symbols.

3. δ is the transition function, You can see that the machine is reading one input symbol and transiting to the next state. This transition can be formally written as δ: Q x Σ => Q

4. q0 is the initial state of the machine. It is the state which has an arrow behind it. Every machine has only one initial state.

5. F is the set of the final states. You can see that some states having double circles, those are the final states.

Now, that we have understood what is DFA, let's see how it really works. So, Here you pass some string to the machine. A string can be anything like 01001. It's just generated based on the grammar. You can check it by yourself, start from the initial state and give one symbol each time. The symbol refers to the 0 or 1 in this automata. When we are done reading with the string, check if the control is in a double-circled state (Final State) or a single-circled state. If the control is in a double-circled state then we can say that the string is valid otherwise, the string is invalid.

2. Non-Deterministic Finite Automata (NFA):

Non-deterministic Finite automata is formally defined as a 5 tuple machine M2,i.e.,

M2 = (Q, Σ, δ, q0, F)

Here, Every symbol in the definition is weird, below is the explanation of every symbol:

1. Q is the set of the states, as you can see in the below demonstration q0, q1, and q3 are the states of the machine. The Q set contains all of those states.

2. Σ is the set of input alphabet as you can see the alphabet 0 and 1 in the below example, that is being read by the machine. Those symbols are inputs and Σ is the set containing those symbols.

3. δ is the transition function, You can see that the machine is reading one input symbol and transiting to the next state. This transition can be formally written as δ: Q x Σ => 2^Q

4. q0 is the initial state of the machine. It is the state which has an arrow behind it. Every machine has only one initial state.

5. F is the set of the final states. You can see that some states having double circles, those are the final states.

As you can see in the above example, NFA has multiple moves on a single input symbol. That's the special feature of NFA which is why it is called Non-deterministic.

3. ε-Non-deterministic Finite Automata (ε-NFA):

Before knowing about ε-NFA, we have to understand what this ε symbol is. This ε read as an epsilon whose length is zero. In automata theory, this ε symbol plays a crucial role in accepting a string. In general, If a state read ε symbol, it will stay in the same state but, in the case of ε-NFA, we will move to the next state.

ε-Non-deterministic Finite automata is formally defined as a 5 tuple machine M3,i.e.,

M3 = (Q, Σ, δ, q0, F)

Here, Every symbol in the definition is weird, below is the explanation of every symbol:

1. Q is the set of the states, as you can see in the below demonstration q0, q1, and q2 are the states of the machine. The Q set contains all of those states.

2. Σ is the set of input alphabet as you can see the alphabet 0 and 1 in the below example, that is being read by the machine. Those symbols are inputs and Σ is the set containing those symbols.

3. δ is the transition function, You can see that the machine is reading one input symbol and transiting to the next state. This transition can be formally written as δ: Q x ( Σ U ε ) => 2^Q

4. q0 is the initial state of the machine. It is the state which has an arrow behind it. Every machine has only one initial state.

5. F is the set of the final states. You can see that some states having double circles, those are the final states.

Conclusion

If you have observed that in M1, M2 and M3 there is only one thing that changes per machine. That's the transition function. From this, we can conclude that all the types of finite machines work the same and most of their properties are almost the same. It's just their approach to solving problems is different.

If you have come to this end then, thanks for reading the blog. If you want to see such blogs in the future please subscribe to the new letter.

Thank you, and see you in the next blog.