Automata Theory is an exciting, theoretical branch of computer science. It established
its roots during the 20th Century, as mathematicians began developing - both
theoretically and literally - machines which imitated certain features of man,
completing calculations more quickly and reliably. The word automaton itself, closely related to the
word "automation", denotes automatic processes carrying out the
production of specific processes. Simply stated, automata theory deals with the
logic of computation with respect to simple machines, referred to as automata.
Through automata, computer scientists are able to understand how machines
compute functions and solve problems and more importantly, what it means for a
function to be defined as computable or for a question to be
described as decidable .
Automatons are abstract models of machines that perform
computations on an input by moving through a series of states or
configurations. At each state of the computation, a transition function
determines the next configuration on the basis of a finite portion of the
present configuration. As a result, once the computation reaches an accepting
configuration, it accepts that input. The most general and powerful automata is
the Turing machine.
The major objective of automata theory is to
develop methods by which computer scientists can describe and analyze the
dynamic behavior of discrete systems, in which signals are sampled
periodically. The behavior of these discrete systems is determined by the way
that the system is constructed from storage and combinational elements.
Characteristics of such machines include:
- Inputs: assumed to be sequences of symbols selected from a finite set I of
input signals. Namely, set I is
the set {x1, x,2, x3... xk}
where k is
the number of inputs.
- Outputs: sequences of symbols selected from a finite set Z. Namely, set Z is the set {y1, y2, y3 ... ym} where m is the number of outputs.
- States: finite set Q, whose definition depends on the type of automaton.
Here we provide you some PPT lectures about Automata Theory.
No comments:
Post a Comment