BCA 3RD SEMESTER FLA 2019

WHAT IS AUTOMATA THEORY?

Automata Theory is an area of computer science concerned with the construction of abstract self-propelled computing systems that automatically follow a specified sequence of actions. A Finite Automaton is an automaton having a finite number of states. This lesson explains the essential ideas of Finite Automata, Regular Languages, and Pushdown Automata before moving on to Turing machines and Decidability.

CONNECTION TO CATEGORY THEORY

Following the automata classification into different kinds mentioned in the preceding section, numerous separate categories of automata may be defined. The Cartesian closed category of deterministic automata, sequential machines or sequential automata, and Turing machines with automata homomorphisms defining the arrows between automata contains both categorical limits and colimits. A quintuple of one automaton Ai is mapped onto the quintuple of another automaton Aj via an automata homomorphism. Automata homomorphisms are also known as automata transformations or semigroup homomorphisms when the automaton's state space, S, is specified as a semigroup Sg. In monoidal categories, monoids are also thought to provide an useful environment for automata.