This note covers the deeper Theory of Computation topics that separate regular languages from context-free languages and computable from non-computable problems. PSC questions often ask Chomsky hierarchy, CFG/PDA relation, Turing machine power, undecidability and P vs NP.
Engineering Definitions
CFG
Standard definition: A grammar whose productions have a single nonterminal on the left side.
Exam meaning: Left side मा single nonterminal हुने context-free grammar।
PDA
Standard definition: A finite automaton with a stack used to recognize context-free languages.
Exam meaning: Stack भएको automaton जसले CFL recognize गर्छ।
Turing machine
Standard definition: A mathematical model with finite control, tape and head capable of general computation.
Exam meaning: General computation model: tape, head र finite control भएको machine।
Undecidable problem
Standard definition: A problem for which no algorithm can decide all instances correctly in finite time.
Exam meaning: सबै inputs का लागि finite time मा सही yes/no दिने algorithm नभएको problem।
Concept Teaching
Automata gain power by gaining memory. DFA has finite memory, PDA has stack memory, and Turing machine has unbounded tape. Chomsky hierarchy organizes grammars/languages by generative power. Complexity classes then ask how efficiently decidable problems can be solved.
CFG and PDA
CFG generates CFL; PDA recognizes CFL.
- CFG is used to describe programming-language syntax.
- Parse tree shows derivation structure.
- Ambiguous grammar has more than one parse tree for a string.
- PDA stack allows matching nested structures.
- CFL examples include balanced parentheses and many expression grammars.
Chomsky Hierarchy
Know language classes and machines.
| Type | Grammar/language | Machine |
|---|---|---|
| Type 3 | Regular | Finite automaton |
| Type 2 | Context-free | Pushdown automaton |
| Type 1 | Context-sensitive | Linear bounded automaton |
| Type 0 | Recursively enumerable | Turing machine |
Turing Machine and Decidability
Turing machines model algorithms.
- Tape works as unbounded memory.
- Head reads/writes and moves left/right.
- A decidable language has a TM that halts on all inputs.
- Recognizable language may halt only on accepted strings.
- Halting problem is undecidable.
- Reduction proves undecidability by transforming known hard problem.
P, NP and NP-Complete
Complexity class questions need exact wording.
- P contains problems solvable in polynomial time.
- NP contains problems whose solutions can be verified in polynomial time.
- NP-hard problems are at least as hard as every NP problem.
- NP-complete problems are both in NP and NP-hard.
- P vs NP asks whether every efficiently verifiable problem is efficiently solvable.
Engineering Mechanism
- Choose model based on language memory need.
- Use CFG productions to generate strings.
- Use PDA stack to match nested dependencies.
- Use TM to model general algorithms.
- Use reductions for undecidability and NP-hardness.
- Classify problems by solvability and efficiency.
Diagrams / Models To Draw
- Draw Chomsky hierarchy pyramid.
- Draw PDA with input, stack and finite control.
- Draw Turing machine tape/head/control.
- Draw parse tree for expression grammar.
- Draw P, NP, NP-complete relationship diagram.
Formulas, Algorithms and Rules
- CFG = (V, Sigma, R, S).
- PDA = finite control + input + stack.
- TM = (Q, Sigma, Gamma, delta, q0, qaccept, qreject).
- NP-complete = NP + NP-hard.
- P subseteq NP.
| Concept | Core idea | Exam trap |
|---|---|---|
| CFG | Generates CFL | Ambiguity matters |
| PDA | Recognizes CFL | Stack memory |
| TM | General computation | Can model algorithms |
| Decidable | Halts on all inputs | Different from recognizable |
| NP | Polynomial verification | Not necessarily non-polynomial |
| NP-complete | Hardest in NP | Must be in NP |
Exam Point
- CFG and PDA are equivalent for CFL.
- DFA cannot count arbitrary nested parentheses; PDA can.
- Halting problem is undecidable.
- P is subset of NP.
- NP-hard need not be in NP.
Worked Example
Balanced parentheses are not regular because arbitrary nesting needs unbounded memory, but they are context-free. A PDA pushes “(” and pops for “)”; acceptance requires empty stack and no mismatch.
Subjective Answer Pattern
- Define CFG/PDA/TM.
- Explain Chomsky hierarchy.
- Differentiate decidable and recognizable.
- Explain halting problem/undecidability.
- Define P, NP, NP-hard and NP-complete.
Common Engineering Mistakes
- Saying NP means not polynomial.
- Confusing NP-hard and NP-complete.
- Saying all recognizable languages are decidable.
- Forgetting PDA stack.
- Mixing grammar types.
MCQ Revision
- Which machine recognizes CFL?
- Which problem is undecidable?
- P is subset of what?
- NP-complete means what?
- Type 3 grammar corresponds to what?
- What is PDA memory?
Final Summary
- CFG/PDA handle context-free languages.
- Turing machines model general computation.
- Chomsky hierarchy ranks language classes.
- Some problems are undecidable.
- P vs NP concerns efficient solving versus verification.