Here are some reasons to study automata theory in computer science .
-
Introducation to finite automata
-
Structural Representation
-
Automata and Complexity
Introducation to Finite Automata
Finite automata are a useful model for many kinds of hardware and software.
Software for designing and checking the behaviour of digital circuits
The 'Lexical Analyzer' of a typical compiler, that is ..
the compiler components that break the inputs text into logical units, such as:
identifiers,keywords and punctuations.
Software for scanning large bodies of text ,such as: collections of web pages ,
to find occurences of words, phrases or other patterns .
Software for varifying systems of all types ,that have finite number of distinct states
such as: communications protocols or protocols for secure exchange of information.
Structural Representation
There are two important notations play an important role in the study of automata
and their applications.
Grammers are useful models when software that processes data
with a recursive structure.
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 2 important issues:
What can a computer do at all ?
This study is called decidability and the problem that can be solved
by computer are called decidable.
What can a computer do efficiently ?
This study is called intractability, and the problems that can be solved by
computer using no more time than some slowly growing function of the size of the input are called
tractable.
Posted By -
