Reasons for studying Autamata in Computer Science
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.
Posted By -