1.3. Traditional Branches of Theory in CS¶
1.3.1. Three Traditional Branches of Theory in CS¶
Formal Languages and Automata
Computability
Complexity
1.3.2. 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)?
1.3.3. Computablity¶
Studies the limits of computational systems from a different perspective from FLAAnswers 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?
1.3.4. Complexity¶
The other two branches talk about “what is possible”.Complexity theory is all about performance.ReductionsClassifies problems by their “complexity”Does P = NP?
