Why study Automata Theory ?

There are several reasons to study of automata and complexity is an important part of the core of computer science.

1. Introduction to Finite Automata

2. Structural Representation

3. Automata and Complexity

Introduction to Finite Automata:

Finite Automata are a useful model for many important kinds of hardware and software.

1. Software for designing and checking the behavior of digital circuits

2. The “Lexical analyzer” of a typical compiler , that is , the compiler component that breaks the

    input text into logical units, such as identifiers, keywords, and punctuation.

3. Software for scanning large bodies of text, such as collections of Web pages, to find 

    occurrences of words, phrases, or other patterns.

4. Software for verifying systems of all types that have a finite number of distinct states, such as

    communications protocols or protocols for secure exchange of information.  

Structural Representations:

There are two important notations there are not automation-like, but play an important role in the study of automata and their applications

1. Grammars are useful models when software that processes data with a recursive structure.

2. Regular Expressions are denoted the structure of data, especially text strings.

 Automata and Complexity

Automata are essential for the study of the limits of computation.

There are two important issues.

1. What can a computer do at all? This study is called “decidability”, and the problems that can

     be solved by computer are called “decidable.”.

2. What can a computer do efficiently? This study is called “intractability,” and the problems that  

    can be solved by a computer  using no more time than some slowly growing function of the  

    size of the input are called ”tractable.”Often, we all polynomial functions to be “slowly

    growing”, while functions that grows faster than any polynomial are deemed to grow too fast.