Finite automata

What is finite automata?

Finite automata or finite state machine is the simplest machine that is used for recognizing patterns. It is an abstract machine that has five elements or tuples. It possesses a set of states and rules that are used for moving from one state to another, but it is dependent on the applied input symbol.

Essentially, it is pretty much an abstract model of a digital computer. It is a mathematical model of computation. 

This abstract machine can be in exactly one of a finite number of states at any given time. The Finite-State Machine (FSM) can be in exactly one of a finite number of states at any specific time.

A finite state machine can transition or change from one state to another in response to some inputs. A finite automaton is defined by a list of its states, its initial state, and the inputs that trigger each transition.

You can observe the behavior of state machines in various devices in modern society that perform a predetermined sequence of actions depending on the sequence of events with which they are presented.

The finite state machine possesses less computational power than certain other models of computation like the Turing machine. The computational power distinction signifies that there are tasks there are computational tasks that a Turing machine could perform but finite automata can’t.

‍

What are the applications of finite automata?

After understanding what is finite automata and it has several applications. Some of them are:

• They are very important in designing lexical scanners. 
• They are also critical in designing spell checkers.
• They are vital in sequential circuit design (transducer)
• They are particularly useful in designing text editors.

In addition to these applications, finite state machines are also used in linguistics, computer science, electrical engineering, biology, philosophy, mathematics,  video game programming, and logic.

In the domain of computer science, are utilized for modeling of application behavior, design of hardware digital systems, software engineering, compilers, network protocols, and studying computation and languages.

Finite automata is also used widely for modeling reactive systems presented here.

‍

‍

What is deterministic finite automaton?

DFA is short for Deterministic Finite Automaton. A finite automata is considered to be deterministic if there is a single resultant state (only one transition) corresponding to an input symbol. 

A deterministic finite automaton is a set of five tuples. It is represented as:

M = {Q, , , q0, F}

Here,

Q is a non empty finite set whose elements are known as states.

is a non empty finite set of input symbols known as the input alphabet

is a transition function  that takes two arguments, a state and an input symbol, it returns a single state. 

q0 is the starting state. It is one of the states in  Q. 

F is a non-empty set of final states or accepting states from the set that belongs to Q.

‍

What is nondeterministic finite automaton?

NFA is short for Nondeterministic Finite Automaton. A finite automata can be considered to be non-deterministic if it has more than one possible transition from one state on the same input symbol. 

A non-deterministic finite automaton also happens to be a set of five tuples and a is formally represented as:

M = {Q, , , q0, F}

Here,

Q is a set of non-empty finite states. 

is a set of non-empty finite input symbols.

is the transition function. It takes a state from Q and an input symbol from  and returns a subset of Q.

q0is the initial state of the non-deterministic automata and is a member of Q.

F is a non-empty set of final states and is a member of Q.

Here are the major differences between a DFA and an NFA:

• A DFA can be considered to be one machine. An NFA can be considered to be a multitude of little machines that are computing simultaneously.
• The next possible state in a DFA is distinctly set. But every pair of state and input symbols can have many possible next states in an NFA.
• DFAs are harder to construct while NFAs are easier to construct.
• NFAs can use Empty String transition while DFAs cannot do that.
• A DFA takes less time to execute an input string while an NFA takes more time to do that.
• A DFA will reject the string if it terminates in a state that is different from the accepting state. An NFA will reject the string if all the branches die or refuse the string.
• DFAs take up more space than NFAs.
• Dead state might be required in a DFA, but it is not required in an NFA.

‍

What are the types of finite automata?

In addition to the deterministic and non-deterministic classification, finite automata can also be classified as acceptors, classifiers, transducers and sequencers.

1. Acceptors

These are also known as detectors or recognizers. They generate binary output, indicating whether  the received input is accepted or rejected. After all the input is received, if the current state is an accepting state, the input is accepted. If the current state is not an accepting state, the input is rejected.

2. Classifiers

Classifiers are a generalization of acceptors which generate n-ary output, where n is strictly a larger number than two.

3. Transducers

Transducers generate output on the basis of a given input or a state using actions. They are widely used in control applications nad in the field of computational linguistics.

4. Sequencers

Sequencers are also known as generators. They are a subclass of acceptors and transducers that have a single-letter input alphabet. They only generate a single sequence that can be considered to be an output sequence of acceptor or transducer outputs.

‍

Does finite automata have memory?

Finite automata does not have any auxiliary storage. It remembers things by changing states. The memory is present in the form of states Q only and according to automata principal. Since any automata can only have finite states, you could say that finite automata has finite memory.

What are the advantages of finite automata?

The advantages of finite automata are:

• Finite automata is flexible
• It is easy to go from a significant abstract to a code execution
• There is a rather low processor overhead.
• The reachability of a state can be easily determined.