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
- Design a finite automaton that accepts strings matching a given pattern
- Write a regular expression and convert it to an equivalent automaton
- Show why a language like balanced parentheses needs a pushdown automaton
- Explain the halting problem and why it has no general solution
- Describe the phases a compiler runs from source text to machine code
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.
Other units in this stage
Back to the full Computer Science roadmap