TOC

2.1 [GATE 1987 : 2 Marks] A context-free grammar is ambiguous if(a) the grammar contains useless non-terminals(b) it produces more than one parse tree for some sentence(c) some production has two non-terminals side by side on RHS(d) None of the above Answer: (b) it produces more than one parse tree for some sentenceConcept: Ambiguity =

Q 3.21 [2006 : 2 Marks]Question: Which of the following problems is undecidable?(a) Membership problem for CFGs(b) Ambiguity problem for CFGs(c) Finiteness problem for FSAs(d) Equivalence problem for FSAsAnswer: (b) Ambiguity problem for CFGsSolution (Hindi + English):FSA ke saare problems Decidable hote hain – Membership, Finiteness, Equivalence, Emptiness sab decidable.CFG ka Membership Decidable hai –

Q1. Which of the following problems are undecidable? A) Membership problem in CFL B) Whether a given CFL is regular C) Whether a FA halts on all inputs D) Membership problem for Type-0 Answer: B, D Explain (Hindi): B – CFL regular hai ya nahi ye check karna undecidable hai (Rice theorem). D – Type-0

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