.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Cliff Shaffer
   :requires:
   :satisfies:
   :topic: CS Theory

.. slideconf::
   :autoslides: False


Traditional Branches of Theory in CS
====================================

.. slide:: Three Traditional Branches of Theory in CS

   * Formal Languages and Automata
   * Computability
   * Complexity

     
.. slide:: Formal Languages and Automata
           
   | Studies the limits to computational systems like grammars and
     automata.
   |  Answers questions like these:
   |    What languages are represented/accepted by a grammar or
        machine?
   |    Are two representations equivalent (accept the same languages)?

       
.. slide:: Computablity

   | Studies the limits of computational systems from a different
     perspective from FLA
   | Answers questions like these:
   |   Can an artifact of this system solve a given problem?
   |   Can we answer questions about the capabilities of an artifact?
   |     Does it halt on given input?
   |     Do two artifacts do the same thing?

       
.. slide:: Complexity

   | The other two branches talk about "what is possible".
   | Complexity theory is all about performance.
   |   Reductions
   |   Classifies problems by their "complexity"
   |     Does P = NP?