Theory of Computation – Core Concepts
(GATE – CS Core Concepts – Beginner Friendly)
Goal: Understand the basic ideas that let us talk about “what can be computed” and “how hard it is.”
Style: Short sentences, everyday analogies, no heavy math or jargon.
1. What Is “Computation”?
- Think of a recipe that takes input (ingredients) and gives output (dish).
- In computer science, the recipe is a machine that reads symbols one by one and decides something (accept/reject, produce a number).
2. Simple Machines – The Building Blocks
| Machine | Everyday Analogy | What It Can Do |
|---|---|---|
| Finite Automaton (DFA) | A vending machine that accepts coins and gives a snack | Recognizes simple patterns (e.g., strings ending in “ab”) |
| Pushdown Automaton (PDA) | A stack of plates that you add or remove | Handles nested patterns (e.g., matched parentheses) |
| Turing Machine (TM) | A robot with a tape that can read/write and move left/right | Can simulate any algorithm (the most powerful machine) |
Key idea: Each machine has a state (where it is) and a memory (tiny for DFA, stack for PDA, tape for TM).
3. Languages – The “Foods” These Machines Recognize
- Language = A set of strings (e.g., all strings of 0s and 1s that start with 1).
- Regular Language
- Recognized by a DFA.
- Think of a simple filter: “All strings that end with the letters “ab”.”
- Context‑Free Language
- Recognized by a PDA.
- Think of matching brackets: “Every ‘(’ has a closing ‘)’. ”
Tiny Example
| Language | DFA Sketch | PDA Sketch |
|---|---|---|
| Strings ending in “ab” | q0 --a--> q1 --b--> q2 (accept) |
Same as DFA (no stack needed) |
| Balanced parentheses | Not regular (cannot be done by DFA) | PDA with stack pushes for '(' and pops for ')' |
4. How We Tell If a Language Is Regular
4.1 Closure Properties
- Adding or removing symbols, joining two languages, or reversing strings stays regular.
- Analogy: Paint colors mix; if you mix two valid colors you still get a valid color.
4.2 Pumping Lemma (simple version)
- For any regular language, long enough strings can be “pumped” (a part can be repeated) and still stay in the language.
- If you find a string that cannot be pumped, the language is not regular.
Tiny Test:
Language = { all strings of equal number of 0s and 1s }
- Pick a long string like
0000011111. - Try to pump a middle part; you’ll break the balance → not regular.
5. Decidability – Can We Always Answer?
- Decidable: There is a machine that always gives the right answer in finite time.
- Example: “Does a given DFA accept the string “abba”?” → Yes, we can run it.
- Undecidable: No machine can answer every instance.
- Classic example: Halting Problem – “Will this TM stop on input 0?”
- Analogy: Trying to know if a person will ever arrive at a destination if they can wander forever.
6. Complexity – How Long It Takes
| Measure | What It Means | Everyday Analogy |
|---|---|---|
| Time Complexity | How many steps for input of length n | Time to boil water (minutes) |
| Space Complexity | How much memory for input n | Size of a backpack |
| Big‑O Notation | Roughly the “upper bound” of steps | “At most a few minutes” |
Tiny Example (DFA for “ends with ab”)
- For a string of length n, the DFA looks at each symbol once.
- Time = O(n) (linear).
- Space = O(1) (only a few states).
7. Quick Recap in One Paragraph
A computer is like a machine that reads symbols and changes state.
- Finite machines (tiny memory) can do simple pattern checks (regular languages).
- Stack machines can handle nested patterns (context‑free languages).
- Turing machines are the most powerful: they can simulate any algorithm but may get stuck forever (undecidability).
- We use tools like the pumping lemma to prove languages are not regular, and we talk about how fast/slow a machine is with time and space complexity.