1.Three Traditional Branches of Theory in CS§

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)?

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?

The other two branches talk about “what is possible”.

Complexity theory is all about performance.

Reductions

Classifies problems by their “complexity”

Does P = NP?