Theory of Computation

Theory of Computation

1. Finite State Machines

   • A finite state machine is a model of computation used to design programs and sequential logic circuits

2. Regular Expression

3. Regular Language

   • A language is called regular if it can be represented by a regular expression
   • It can also be defined as any language that a finite state machine will accept

4. Backus-Naur Form

   • Meta-Languages
     • In order for a computer language to be translated into machine code, all rules of the language must be defined unambiguously
     • Backus-Naur Form is an example of one such meta-language. Many constructs that could be written using a regular expression can be expressed more succinctly using BNF

5. Big-O Notation

6. Limits of computation

   • Tractable problems
     • Tractable problems are problems which a computer can solve but it would take a complexity of time
     • O(n^k)
     • O(n)
     • O(n log n)
     • O(n^10)
   • Intractable problems
     • Is a problem which does not have a polynomial-time solution.
     • O(2^n)
     • O(n!)

7. Heuristic Methods

   • Solving a problem which uses an algorithm or method which is not guaranteed to be optimal or perfect but is sufficient for the purpose
   • It won't solve all the problems but it must solve most/many
   • Virus scanners use this approach

8. The Halting Problem

   • The Halting problem is the problem of determining whether for a given input, a program will finish running or continue forever.
   • The Halting problem demonstrates that there are some problems that cannot be solved by a computer.

9. Turing Machine

   • It consists of an infinitely long strip of tape divided into squares. It has a read/write head that can read symbols from the tape and make decisions about wha to do based on the contents of the cell and its state

Imagens e arquivos do mapa