Skip to main content

Here are some reasons to study automata theory in computer science .

  1. Introducation to finite automata
  2. Structural Representation
  3. 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.