**What is an automaton?**

An automaton is a recognizer i.e given an input language, it recognizes if a string is a part of that language.

For Eg. English is a language comprising of alphabets ‘a-z’, “beethoven” word is a valid string of the language. At the same time “!a89rr” is an invalid string.

**Terms involved in modeling a Finite State machine**

*Start State* – The initial state of the system when no interaction has taken place yet

*End/Accepting State* – The state(s) that indicates the successful operation of a system (Eg. acceptance of a string)

*Transition* – An action which triggers the change of the system from one state to another

**Mathematical Definition [ Wikipedia ]**

A *deterministic finite state machine* or *acceptor deterministic finite state machine* is a quintuple **(Σ,***S*,*s*_{0},δ,*F*), where:

- Σ is the input alphabet (a finite, non-empty set of symbols).
*S* is a finite, non-empty set of states.
*s*_{0} is an initial state, an element of *S*.
- δ is the state-transition function: (in a nondeterministic finite state machine it would be , ie., δ would return a set of states).
*F* is the set of final states, a (possibly empty) subset of *S*.

**Graphical Representation**

An automata is represented graphically using a *state diagram* where each state is represented by a circle and transitions are represented by arrows labeled with the input alphabet causing the transition.

Finite State Machine

Eg. A Finite state Machine which recognizes if the input string has even number of zeros

There are only 2 possible states for a string “Even number of zeroes” or “Odd number of zeroes”.The initial state, an empty string has even zeroes. Hence, the start state is the end/accepting state. This FSM can be represented by

Even -> 1 = Even

Odd -> 0= Even

Even -> 0=Odd

Odd -> 1=Odd

Here, ” -> ” represents a transition and ” = ” represents the change to the next state. [ Assumed ]

The language accepted by the FSM is {00,100,1100,110000,10000, . . . } . The set of strings generated is infinite