Introduction to Automata

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,s0,δ,F), where:

  • Σ is the input alphabet (a finite, non-empty set of symbols).
  • S is a finite, non-empty set of states.
  • s0 is an initial state, an element of S.
  • δ is the state-transition function: \delta: S \times \Sigma \rightarrow S (in a nondeterministic finite state machine it would be \delta: S \times \Sigma \rightarrow \mathcal{P}(S), 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

Advertisements
By V Posted in TOC

3 comments on “Introduction to Automata

  1. Pingback: Modelling Automata using Graphwiz API « From Patronizing to Patriotic

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s