Automata Theory Abstract Computing Concepts

Automata Theory Abstract Computing Concepts

Automata Theory Abstract Computing ConceptsDefinition of Automata Theory Abstract Computing Concepts – The automata theory is a branch of Computer Science which relates the study of Abstract Computing devices or machine. Alternatively automata deals with the logic of computations with respect to simple machines. The automata play a vital role in theory of computation, compiler construction, parsing, artificial intelligence and format verification.

What is Automaton?

The abstract model of machine that perform computations on an input by moving through a series of states and configuration is known as Automatons. This automation consists of states and transitions. The automation is supposed to run on some given sequence of inputs in discrete time frames. The major goal of automata theory is to develop methods by which computer technocrats or scientists can describe and analyse the dynamic behaviour of discrete systems. The major characteristics/ terms of these machines contains – Inputs, Outputs and states. This theory is closely related to formal language theory.

Automaton in Conceptual Terms

An automation is a mathematical object that takes a word as input and decides either to accept it or reject it. An automaton with a finite no of states is called as Finite automation or Finite state machine. A deterministic finite automation is represented formally by a tuple consisting 5 objects – (Q,Σ,δ,q0,F)

  1. Q – It is a finite set of states.
  2. Σ – It is a finite set of symbols called the alphabet of the automation.
  3. δ  – it is the transition functions i.e. – δ : Q × Σ → Q
  4. q0 – it is the start states, where q0 Q.
  5. F – It is the set of states of Q called accept states.

Four Types of Automaton:

  1. Finite State Machine – The automaton in which the state set Q contains only a finite number of elements is called finite state machine (FSM). The FSM consists of set of states, set of input events, a set of output events and a state transition functions.
  2. Pushdown Automata – The automaton which uses stack for processing input and output states. These automata is more capable than finite state machine but less capable than Turing Machine.
  3. Linear bounded Automata – It is a non-deterministic Turing machine which satisfy three conditions. A. Its Input contains two special symbols – left and right end markers. B. transitions may not print other symbols over the end markers. C. transition neither move to the left of end marker nor right of the end marker.
  4. Turing Machine – it is the abstract machine that manipulates symbols on a strip of tape and capable of simulating algorithms logic. The machine operates on an infinite memory tape which is further divided into discrete cells. The Turing machine was invented in 1936 by Alan Turing. The Automata Theory Abstract Computing Concepts exists in this machine.

Leave a Reply