Automata

Introduction to Automata:

Automata theory is the study of abstract computing devices or “machines”. Before there was a computer, in the 1930’s.A Turing studies an abstract machine that had all the capabilities of today’s computers, at least as far as in what they could compute.

Turing’s goal was to describe precisely the boundary between what a computing machine could do and what it could not do; his conclusions apply not only to his abstract Turing machines, but to today’s real machine

A “final automata”, originally proposed to model brain function, turned out to be extremely useful for a variety of other purposes.

N.Chomsky began the study of formal “grammars.” While not strictly machines, these grammars have close relationships to abstract automata and server today as the basic of some important software components, including parts of compilers.

Cook was able to separate those problems that can be solved, but in practice take so much time that computers are unless for all but very small instances of the problem. The latter class of problems is called “intractable”, or “NP-hard”.

All of these theoretical developments bear directly on what computer scientists do today. Some of the concepts, like finite automata and certain kinds of formal grammars are used in the design and construction of important kinds of software.