**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.

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=OddHere, ” -> ” 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

Pingback:Modelling Automata using Graphwiz API « From Patronizing to PatrioticThis(Theory of Automation) is one subject that makes me shiver whenever i hear its name.

Well, to be frank, it took me some time to grasp the concepts too, but I was interested mainly because of the way my project guide explained it to me. It sounded so boring while it was taken in class, but he made it sound so interesting.