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 matlab RE language, usme membership check undecidable hota hai.[1989]Q2. It is undecidable whether:
A) TM halts after 10 steps
B) TM ever prints a specific letter
C) TM computes product of two numbers
D) None
Answer: B, C
Explain: A to decidable hai, bas 10 step simulate karo. B aur C function ka property hai, Rice theorem se undecidable.[1990]Q3. Recursive languages are:
A) Proper superset of CFL
B) Can be recognized by TM
C) Can be recognized by FA
D) A and B
Answer: D
Explain: Recursive = TM jo har input pe halt kare. Ye CFL se bada hai aur TM se recognize hota hai.[1990]Q4. Finite language is?
A) Non-regular B) Not CFL C) Regular D) None
Answer: C – Regular
Explain: Finite language ka hamesha DFA ban jata hai, isliye Regular.[1991]Q5. For every non-deterministic M1 there is deterministic M2?
A) NFA to DFA B) NPDA to DPDA C) NTM to DTM
Answer: A and C possible, B not possible
Explain: NPDA, DPDA se zyada powerful hai, isliye convert nahi hota. Ye GATE ka sabse bada trap hai.[1992]Q6. Which conversion is not possible?
A) NFA to DFA B) NTM to DTM C) NPDA to DPDA D) Regular to CFG
Answer: C
Explain: Same reason.[1994]Q7. Which statement is FALSE?
A) Emptiness of Type-0 is undecidable
B) Emptiness of TM is undecidable
C) Equivalence of 2 CFG is undecidable
D) Equivalence of 2 Regular Grammar is undecidable
Answer: D is FALSE
Explain: 2 Regular Grammar equal hai ya nahi ye DECIDABLE hota hai, isliye D wala jhooth hai.[1996]Q8. Which is NOT decidable?
A) Equivalence of 2 FSM B) Equivalence of 2 TM C) FSM accepts w D) Finiteness of Regular
Answer: B
Explain: 2 TM same language accept karte hain ya nahi, ye undecidable hai.[1997]Q9. Which equivalence is FALSE?
A) NFA = DFA B) NPDA = DPDA C) NTM = DTM D) Single tape = Multi tape TM
Answer: B is FALSE
Explain: NPDA!= DPDA.[1998]Q10. Which is true?
A) Complement of recursive is recursive
B) Complement of RE is RE
C) Complement of recursive is RE
D) Complement of CFL is CFL
Answer: A
Explain: Recursive TM ka YES/NO ulta kar do to complement bhi recursive.[2002]Q11. C language is?
A) Regular B) Context Sensitive C) CFL D) None
Answer: B – CSL
Explain: C me declaration check karna CFG se nahi hota, isliye CSL.[2002]Q12. P1: Does FSM accept string? P2: Does CFG generate infinite strings?
Answer: Both Decidable
Explain: FSM ko chalao. CFG me loop A=>_..A.. hai to infinite.[2002]Q13. Given TM M, state q, word w, does M visit q?
Answer: Undecidable but partially decidable (RE)
Explain: Visit karega to pata chal jayega (RE), nahi karega to kabhi sure nahi.[2002]Q14. L = (0+1)_ if P=NP else Φ
Answer: A – Recursive
Explain: Dono case me L Regular hai, Regular to Recursive hota hi hai.[2003]
Q15. GATE 2003
If the strings of a language L can be effectively enumerated in lexicographic (alphabetical) order, then L is:
(A) Regular but not necessarily context-free
(B) Context-free but not necessarily regular
(C) Context-free but not necessarily recursive
(D) Recursive but not necessarily context-free
Answer: (D)
Explain: Lex order me list kar sakte ho matlab har string ka bata sakte ho L me hai ya nahi, to ye Recursive hai. Par ye CFL ho zaruri nahi.Q16. GATE 2003
Consider a single tape TM table given in your book. What is language recognized by M?
(A) M does not halt on any string in (0+1)+
(B) M halts on all strings in (0+1)+
(C) M accepts {0}
(D) M accepts {1}
Answer: (A)
Explain: q0 pe 0/1 dekha to 1 likh ke right, q1 pe Blank dekha to left q0 pe. q0->q1->q0 ka infinite loop, kabhi HALT state pe nahi jayega. Isliye non-empty string pe halt nahi karega.Q17. GATE 2005
Let P1 be decidable, P2 be undecidable. Which statement is true for P3?
(A) P3 decidable if P1 reducible to P3
(B) P3 undecidable if P2 reducible to P3
(C) P3 undecidable if P3 reducible to P2
(D) P3 decidable if P3 reducible to complement of P2
Answer: (B)
Explain: Rule yaad rakh – Agar Undecidable <= P3 to P3 bhi Undecidable. Yahan P2 Undecidable hai aur P2 <= P3 hai.
Q18. GATE 2005
Let L1 be recursive, L2 be RE but not recursive. Then:
(A) L1 complement is recursive, L2 complement is recursive
(B) L1 complement is recursive, L2 complement is NOT RE
(C) Both complements are RE
(D) Both complements are not RE
Answer: (B)
Explain: Recursive ka complement hamesha Recursive. RE jo recursive nahi hai uska complement kabhi RE bhi nahi hota, warna wo recursive ban jata.Q19. GATE 2006
L = { s | d(s) mod5=2 and d(s) mod7≠4 } where d(s) is decimal value of binary string s. L is:
(A) Not recursive
(B) Recursive but not CFL
(C) CFL but not regular
(D) Regular
Answer: (D) Regular
Explain: Mod 5 aur Mod 7 yaad rakhne ke liye sirf 5*7=35 states ka DFA chahiye. Isliye Regular.Q20. GATE 2006
L1=Regular, L2=DCFL, L3=RE but not recursive. Which is FALSE?
(A) L1 ∩ L2 is DCFL
(B) L2 ∩ L3 is recursive
(C) L1 ∪ L3 is RE
(D) L1 ∩ L2 ∩ L3 is RE
Answer: (B) is FALSE
Explain: L2 to Recursive hai par L3 ka membership undecidable hai. Isliye L2 ∩ L3 ka membership check nahi kar sakte, to wo Recursive nahi hoga.Q21. GATE 2007
Which problem is undecidable?
(A) Membership problem for CFG
(B) Ambiguity problem for CFG
(C) Finiteness problem for FSA
(D) Equivalence problem for FSA
Answer: (B) Ambiguity problem for CFG
Explain: CFG ambiguous hai ya nahi ye check karna undecidable hai. Baaki FSA wale sab decidable.
Q22. GATE 2008
Language L = { a^p | p is prime } is:
(A) Regular
(B) CFL but not regular
(C) CSL but not CFL
(D) Neither regular nor CFL but accepted by TM
Answer: (D)
Explain: Prime ko pump nahi kar sakte, isliye na Regular na CFL. Par TM me program likh ke prime check kar sakte hain.
Q23. GATE 2008
If L and complement of L both are RE, then L is:
(A) Regular (B) CFL (C) CSL (D) Recursive
Answer: (D) Recursive
Explain: Theorem yaad rakh - RE + co-RE = Recursive.Q24. GATE 2008
Which problems are decidable?Whether intersection of two regular languages is infiniteWhether a given CFG is regularWhether two PDA accept same languageWhether a given grammar is context-free
(A) 1 and 2 (B) 1 and 4 (C) 2 and 3 (D) 3 and 4Answer: (B) 1 and 4
Explain: 1. Regular intersection infinite hai ya nahi - DFA me cycle dekho, decidable. 4. Grammar CFG hai ya nahi - form dekho A->…, decidable. 2 aur 3 undecidable hain.Q25. GATE 2010
L1 recursive, L2 and L3 are RE but not recursive. Which is NOT necessarily true?
(A) L1 – L2 is RE
(B) L2 – L1 is RE
(C) L1 ∩ (L2 ∪ L3) is RE
(D) L2 ∪ L3 is RE
Answer: (A) is NOT necessarily true
Explain: L1-L2 = L1 ∩ L2-bar. L2-bar to RE bhi nahi hai, to ye RE ho zaruri nahi. (B) me L2-L1 = L2 ∩ L1-bar = RE ∩ Recursive = RE hamesha true hai.Q26. GATE 2011
Which pair have DIFFERENT power?
(A) Single-tape TM and Multi-tape TM
(B) DPDA and NPDA
(C) DFA and NFA
(D) DTM and NTM
Answer: (B) DPDA and NPDA
Explain: Sirf inki power alag hai, NPDA zyada powerful hai.Q27. GATE 2012
Which problems are decidable?Does program ever produce output?If L is CFL, is complement also CFL?If L is regular, is complement also regular?If L is recursive, is complement also recursive?
(A) 1,2 (B) 2,3 (C) 1,4 (D) 3,4Answer: (D) 3,4
Explain: 3. Regular ka complement Regular – hamesha true, decidable. 4. Recursive ka complement Recursive – hamesha true, decidable. 1 aur 2 undecidable.