RGPV short note on automata

RGPV 2010
Q. Write short note on automaton?

Ans. An automaton is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically.
There are four major families of automaton :
  1. Finite-state machine.
  2. Pushdown automata.
  3. Linear-bounded automata.
  4. Turing machine.
1. Finite-state machine: A system where particular inputs cause particular changes in state can be represented using finite state machines. In it a state machine will read a series of inputs. When it reads an input, it will switch to a different state. Each state specifies which state to switch to, for a given input.

2. Pushdown automata: Pushdown automata are nondeterministic finite state machines augmented with additional memory in the form of a stack.

3. Linear-bounded automata: A linear bounded automaton is a nondeterministic Turing machine that satisfies the following three conditions:

  1. Its input alphabet includes two special symbols, serving as left and right endmarkers. 
  2. Its transitions may not print other symbols over the endmarkers.
  3. Its transitions may neither move to the left of the left endmarker nor to the right of the right endmarker.

4. Turing Machine: A Turing Machine is an accepting device which accepts the languages (recursively enumerable set) generated by type 0 grammars.