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

- Finite-state machine.
- Pushdown automata.
- Linear-bounded automata.
- 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:

- Its input alphabet includes two special symbols, serving as left and right endmarkers.
- Its transitions may not print other symbols over the endmarkers.
- 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.