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 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.
q0: the initial state
F: set of accepting state

Example

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

FA for strings starting with aa

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

state For input a For anything else
a1 a2 never
a2 okay never
never never never
okay okay okay

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.

Symbol for a Non accepting State in FA

Accepting States

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

Symbol for an Accepting State in FA

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.

Symbol for Trap State in FA

State Transition

Symbol for state transition in FA

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

Join Discussions

XPLAIND.com is a free educational website; of students, by students, and for students. You are welcome to learn a range of topics from accounting, economics, finance and more. We hope you like the work that has been done, and if you have any suggestions, your feedback is highly valuable. Let's connect!

Copyright © 2010-2019 XPLAIND.com