Theory of Computation Topics - GATE CS & IT Syllabus

1

Patterns for strings using operators: concatenation, union (*, +, ?).

1m2/10

📌 Key FormulaKleene star: zero or more.

2

DFA and NFA: finite state machines for recognizing regular languages.

1m3/10

📌 Key FormulaNFA to DFA conversion (subset construction).

3

CFG: production rules A → α, used for context-free languages.

1m3/10

📌 Key FormulaDerivations, parse trees, ambiguity.

4

PDA: finite automaton with stack memory.

3/10

📌 Key FormulaAcceptance by final state or empty stack.

5

Properties, closure under operations, pumping lemma for regular and CFL.

2m4/10

📌 Key FormulaPumping lemma: if L regular, ∃p such that any string length≥p can be pumped.

6

Tool to prove that a language is not regular or not context-free.

1m4/10

📌 Key FormulaFor regular: ∃p s.t. ∀|s|≥p, s=xyz, |xy|≤p, |y|>0, xy^iz∈L.

7

TM as model of computation; decidability, halting problem, reducibility.

2m4/10

📌 Key FormulaHalting problem is undecidable.