Finite Automaton

Finite automaton is a machine used to recognize patterns. FA accepts or rejects an input based on already defined set of strings known as the language of the automaton.

A finite automaton/machine has a finite number of states where a state can either be an accepting state or rejecting state. It takes a sequence of input and changes its current state pointer according to the rules of the machine known as the state function. After the input sequence ends the current state of the machine determines whether the input is accepted or rejected based on the type of the state. In other words, if the current/active state of a machine after the input given ends, is an accepting state the input is known to be accepted and vice versa.

Hence a finite automaton is designed to result in an accepting state if the input lies in the language (set of strings) we want to recognize. Also vice versa.

A simple fa example is that of airplane safety control. It tracks the state of the airplane, like fuel, doors open, fins operating etc. Different events change the state of the airplane safety control, which might either result into an accepting state (allowing to start the engine and takeoff) or a rejecting state if the airplane is not in a condition for a safe flight.

Methamatical Representation

A finite automaton is mathematically represented by

$$ (\text{Q} \text{,} Σ \text{,} δ \text{,} \text{q} \text{0} \text{,} \text{F} ) $$

Where,
Q: set of all states.
Σ(Alphabet): all possible symbols for an input.
δ (Transition Function): the rules which specify the next state.
q₀: the initial state
F: set of accepting state

Example

Let's create FA which accepts strings starting with 'aa'

Here,
Q: {a1,a2,okay,never}
Σ(Alphabet): {a,b,c, ....} (finite)
q₀: 'no input yet'
F: {okay}
δ (Transition Function):

Design & Symbols

Finite automaton can also be represented graphically to easily understand what is going on. Trying to understand the language of a machine through its state transition function is very difficult. The sate transition function is good for computers while human find the state diagram more comfortable.

Non Accepting/Rejecting States

Non accepting states are the sates at which if the input string ends the input is considered to be rejected.

Accepting States

Accepting states are the sates at which if the input string ends the input is considered to be accepted.

Trap States

For some languages a machine can determine if a string is valid or invalid in early stage and after which no symbol has any effect on the result such a state is known as a trap state.

State Transition

where the transition symbol is the character in the input which results in the transition.

Types

Different types of finite automata are

1. Deterministic finite automata
2. Nondeterministic finite automata

Let’s discuss the examples there.

by Arifullah Jan and last modified on Mar 27, 2020