Complete TOC Notes for GATE CSE 2026 – Finite Automata to Turing Machine

Theory of Computation (TOC) GATE CSE ka sabse conceptual subject hai. Har saal 4-6 marks aate hain. Isme se DFA Minimization, Undecidability aur PDA se direct question aata hai. Ye mera best subject hai, isliye ye notes 100% Unique aur PYQ Pattern par banaye hain.

1. Regular Language and Finite Automata – Base

DFA (Deterministic): Har state se har input par ek hi transition. n states se max 2^n states ka language. Dead State ya Trap State hota hai.

NFA (Non-Deterministic): Ek state se ek input par multiple transition. Epsilon transition ho sakta hai. NFA se DFA conversion me 2^n states ban sakte hain. Subset Construction Method use hota hai.

Regular Expression: 0* = Epsilon + 0 + 00… , 0+ = 0.0* . GATE me Regular Expression se DFA banana poochte hain. Arden’s Theorem se Regular Expression nikalte hain: R = Q + RP to R = QP*.

GATE Trick: Number of states in Minimal DFA = Number of equivalence classes in Myhill-Nerode Theorem. Myhill-Nerode se Minimal DFA kaise nikalte hain, ye har saal aata hai.

2. DFA Minimization and Properties

Minimization ke liye 2 State ko distinguish karna padta hai. Table Filling Method (Marking Method) best hai. Final aur Non-Final kabhi equivalent nahi hote.

Closure Properties: Regular Language Union, Intersection, Complement, Reverse, Kleene Star me Closed hai. Intersection me Closed hai isliye do Regular ka Intersection bhi Regular hota hai.

Pumping Lemma for Regular: Agar koi language Regular hai to usko pump kar sakte hain. Iska use Non-Regular prove karne me hota hai. L = {0^n1^n} Non-Regular hai, Regular nahi hai.

3. Context Free Language and PDA – Most Important

CFG: A -> aAb | epsilon. Isse 0^n1^n banta hai. CFG se language kaise banti hai ye samajhna zaroori hai. Ambiguous Grammar me ek string ke 2 parse tree bante hain.

CNF (Chomsky Normal Form): A -> BC ya A -> a. CYK Algorithm CNF par hi chalta hai. GNF me A -> aX jahan X variables ka string.

PDA (Push Down Automata): FA + Stack. Stack ki wajah se 0^n1^n accept kar leta hai jo DFA nahi kar pata. NPDA, DPDA. Har DCFL ka DPDA hota hai lekin har CFL ka DPDA nahi hota. L = {ww^R} DCFL hai, DPDA se accept hota hai.

Pumping Lemma for CFL: L = {a^n b^n c^n} CFL bhi nahi hai, CSL hai. L = {0^n1^n2^n} bhi CFL nahi hai.

4. Turing Machine and Decidability – GATE ka Favorite

Turing Machine: Sabse powerful machine. Infinite Tape. LBA (Linear Bounded Automata) CSL ko accept karta hai.

Recursive vs RE:

• Recursive Language: Hamesha Halt karega, Yes/No bolega. Decidable hai.
• RE Language: Yes par Halt karega, No par Loop me ja sakta hai. Semi-Decidable.
• Not RE: Kabhi Halt nahi karega.

Undecidability – Har Saal 1 Question Pakka:

• Halting Problem of TM is Undecidable.
• Membership problem of CFG is Decidable, but Ambiguity of CFG is Undecidable.
• Emptiness of Regular is Decidable, Emptiness of CFL is Decidable, but Emptiness of CSL is Undecidable.
• Regularity of CFG is Undecidable.
• Equivalence of 2 DFA is Decidable, Equivalence of 2 CFL is Undecidable.

Rice Theorem: RE Language ki koi bhi Non-Trivial Property Undecidable hoti hai. Ye Theorem se GATE me direct True/False poochte hain.

5. Chomsky Hierarchy – Final Revision

Type 3: Regular (DFA), Type 2: CFL (PDA), Type 1: CSL (LBA), Type 0: RE (TM). Type 3 < Type 2 < Type 1 < Type 0.

Final Checklist for TOC: Minimal DFA States, Pumping Lemma se Non-Regular Prove, PDA ka Stack Behavior, Decidability Table (10 Properties yaad rakho). Ye 4 se 5 marks pakke.