Skip to main content

Theory for Computer Sciences

Theory of computation and compilers ask what can be computed and how languages become running programs. Theory covers finite automata, regular expressions, context-free grammars, Turing machines, decidability and the P versus NP question. Compiler study applies the same ideas through lexing, parsing, semantic analysis and code generation.

Stage: Data and Theory · Part of the Computer Science roadmap · Last reviewed 19 November 2026

What to learn in Theory

Theory interview questions

What is the halting problem?

It asks whether a program can decide, for any program and input, whether that program eventually stops. Turing proved that no such general algorithm exists. It is the standard example of an undecidable problem and shows that some questions about programs cannot be answered by any program.

What do P and NP mean?

P is the class of problems solvable in polynomial time. NP is the class whose proposed solutions can be verified in polynomial time. Whether every problem in NP is also in P is an open question, and NP-complete problems like SAT are the hardest ones in NP.

Where Theory fits in the Computer Science roadmap

Theory belongs to the Data and Theory stage (intermediate level), which takes about 53 hours. Higher-level ideas.

Back to the full Computer Science roadmap