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 – CYK algorithm se check kar sakte hain.Lekin CFG ke liye Ambiguity, Equivalence, Universality, Containment ye sab Undecidable hote hain.Isliye (b) sahi hai.Concept:
FSA -> Sab Decidable
CFG -> Membership, Emptiness, Finiteness Decidable. Baaki sab Undecidable.
Q 3.22 [2007 : 1 Mark]Question: Which of the following is true for the language {a^p | p is a prime}?
(a) It is not accepted by a Turing Machine
(b) It is regular but not context-free
(c) It is context-free but not regular
(d) It is neither regular nor context-free, but accepted by a Turing machineAnswer: (d)Solution (Hindi + English):Ye language prime length ki hai. Pumping Lemma se proof hota hai ye Regular nahi hai.CFL ke liye bhi Pumping Lemma fail hota hai, to ye Context-Free bhi nahi hai.Lekin har prime ko Turing Machine check kar sakti hai – trial division karke. Toh ye RE hai aur TM accept karegi.Matlab na Regular, na CFL, par Recursive Enumerable.Formula: L = {a^p | p is prime} is not CFL but is Recursive.
Q 3.23 [2008 : 1 Mark]
Question: If L and L complement (L bar) are recursively enumerable then L is
(a) regular (b) context-free (c) context-sensitive (d) recursiveAnswer: (d) recursive
Solution: (Hindi + English):Ye sabse important theorem hai.Theorem: Agar L aur complement of L dono RE hain, to L Recursive hai.Reason: Dono ke liye TM hogi. Ek TM L ko enumerate karegi, dusri L’ ko. Dono ko parallel chalao, ek na ek to halt karegi hi. Isliye hum decide kar sakte hain.Isliye answer recursive hai.Concept: L is Recursive <=> L and L’ both are RE.
Q 3.24 [GATE 2014 Set-2]
Question: Consider two languages L1 and L2. L1 = { | M takes at least 2016 steps on some input }, L2 = { | M takes at least 2016 steps on all inputs }. Which is true?
Options:
a) Both decidable b) Both undecidable c) L1 decidable L2 undecidable d) L1 undecidable L2 decidable
Answer: (a) Both decidable
Explanation Hinglish: 2016 steps ka matlab TM max 2016 cells hi touch karega. Inputs jo 2016 se bade hain unka pehla 2016 prefix hi matter karta hai. To total check karne wale strings finite ho gaye (2^2016 types). Finite simulation se decide kar sakte hain, isliye dono decidable hain. Ye GATE ka repeated concept hai.Q 3.25 [GATE 2015 Set-1]
Question: Which of the following is/are decidable?
S1: { | L(M) = finite }
S2: { | L(M) = Regular }
Answer: Both Undecidable
Explanation Hinglish: Finiteness aur Regularity dono non-trivial properties hain language ki, Rice’s theorem lagta hai. RE languages ke liye ye check karna undecidable hota hai. Isliye S1, S2 dono undecidable.Q 3.26 [GATE 2015 Set-2]
Question: L1 = { | L(M) contains empty string epsilon }, L2 = { | L(M) is empty }. Which is decidable?
Answer: L1 is RE but undecidable, L2 is undecidable and not even RE. But membership type? Actually L(M) contains epsilon is RE (simulate M on epsilon). Empty is not RE.
Explanation Hinglish: L1 me bas M ko epsilon pe chalao, agar halt and accept kare to YES, ye semi-decidable hai. L2 emptiness problem hai, jo co-RE hai.Q 3.27 [GATE 2016 Set-1]
Question: Which of the following problems is decidable for a given CFG G?
A) Is L(G) = phi? B) Is L(G) = Sigma_? C) Is L(G) regular? D) Is L(G) infinite?
Answer: (A) and (D) are decidable
Explanation Hinglish: CFG ke liye Emptiness aur Finiteness decidable hote hain (useless symbols aur loop check se). Universality (Sigma_) aur Regularity check karna undecidable hai CFG ke liye.Q 3.28 [GATE 2016 Set-2]
Question: Let L be recursive and M be TM that halts on all inputs. Consider: L1 = { | M accepts at least 2 strings }, L2 = { | M accepts at most 2 strings }. Which is decidable?
Answer: Both are undecidable – Actually L1 is RE, L2 is not RE. But as per Rice?
Explanation Hinglish: Language contains at least k strings aur at most k strings dono non-trivial properties hain, isliye Rice’s second theorem se undecidable. Lekin L1 RE hai kyunki dovetailing se 2 strings ka wait kar sakte hain. L2 co-RE bhi nahi.
Q 3.29 [2013 : 2 Marks]
Question: Which of the following is/are undecidable?G is a CFG. Is L(G) = Φ?G is a CFG. Is L(G) = Σ?M is a Turing machine. Is L(M) regular?A is a DFA and N is an NFA. Is L(A) = L(N)? (a) 3 only (b) 3 and 4 only (c) 1,2 and 3 only (d) 2 and 3 onlyAnswer: (d) 2 and 3 onlySolution:1. CFG Emptiness -> Decidable. Derivation se check kar lete hai, CYK se.2. CFG = Σ ? -> Undecidable. Universality of CFG undecidable hai.3. L(M) regular? -> Undecidable. Ye Rice’s theorem ka case hai, TM property undecidable.4. DFA vs NFA equivalence -> Decidable. Dono ko DFA me convert karke equivalence check kar sakte hai.
Isliye 2 and 3 undecidable.Q 3.30 [2014 Set-1 : 2 Marks]
Question: Let L be a language and L bar be its complement. Which one is NOT a viable possibility?
(a) Neither L nor L bar is RE
(b) One of L and L bar is RE but not recursive; the other is not RE
(c) Both L and L bar are RE but not recursive
(d) Both L and L bar are recursiveAnswer: (c)Solution:
Sabse important theorem yaad rakho:Agar L aur L bar dono RE hai => L Recursive hai.Isliye (c) bol raha hai dono RE hai par recursive nahi, ye kabhi possible hi nahi hai. Ye hi NOT viable hai.(a), (b), (d) sab possible cases hain.Q 3.31 [2014 Set-2 : 2 Marks]
Question: Let be encoding of a Turing machine as a string over Σ={0,1}. Let L = { | M is a Turing machine that accepts a string of length 2014}. Then, L is
(a) decidable and RE (b) undecidable but RE (c) undecidable and not RE (d) decidable but not REAnswer: (b) undecidable but RESolution:RE hai: Ek NTM banao jo pe saare length 2014 ke strings (2^2014 strings) ko dovetailing se run kare. Agar koi accept hota hai to accept kar le. Toh ye RE hai.Undecidable hai: Agar ye decidable hota to Halting Problem solve ho jata. Rice’s theorem bhi lagta hai, non-trivial property hai.
Isliye undecidable but RE.Q 3.32 [2014 Set-2 : 1 Mark]
Question: Let A ≤m B denotes that language A is mapping reducible to B. Which one is FALSE?
(a) If A ≤m B and B is recursive then A is recursive
(b) If A ≤m B and A is undecidable then B is undecidable
(c) If A ≤m B and B is RE then A is RE
(d) If A ≤m B and B is not RE then A is not REAnswer: (d)Solution:Mapping reduction me: A ≤m B ka matlab A ka solver B se bana sakte hai.(a), (b), (c) teeno sahi properties hai.(d) FALSE hai: Agar B non-RE hai to A RE ho bhi sakta hai. Example: A = Φ (recursive) aur B = Halting ka complement (non-RE). Φ ≤m B hamesha hota hai par A RE hai. Isliye ye statement galat hai.Q 3.33 [2014 Set-3 : 1 Mark]
Question: Let Σ be a finite non-empty alphabet and let 2^Σ_ be the power set of Σ. Which one is TRUE?
(a) Both 2^Σ and Σ_ are countable (b) 2^Σ_ is countable and Σ_ is uncountable (c) 2^Σ_ is uncountable and Σ_ is countable (d) Both are uncountableAnswer: (c)Solution:Σ_ countable hai: Saare strings ko length ke hisab se list kar sakte hai – a, b, aa, ab… countable infinite.2^Σ_ uncountable hai: Ye power set hai countable set ka. Cantor theorem se power set of countable set is uncountable.
Isliye (c).Q 3.34 [2014 Set-3 : 2 Marks]
Question: Which one of the following problems is undecidable?
(a) Deciding if a given CFG is ambiguous
(b) Deciding if a given string is generated by a given CFG
(c) Deciding if the language generated by a given CFG is empty
(d) Deciding if the language generated by a given CFG is finiteAnswer: (a)Solution:(b) Membership -> Decidable CYK se.(c) Emptiness -> Decidable(d) Finiteness -> Decidable(a) Ambiguity -> Undecidable. Ye yaad rakho.Q 3.35 [2015 Set-1 : 1 Mark]
Question: For any two languages L1 and L2 such that L1 is context-free and L2 is RE but not recursive, which is necessarily true?L1 bar is recursive 2. L2 bar is recursive 3. L1 bar is context-free 4. L1 bar ∪ L2 is REAnswer: (d) 1 and 4 onlySolution:1. True: Har CFL decidable hoti hai, toh CFL recursive hai. Recursive closed under complement, toh L1 bar recursive.2. False: L2 RE but not recursive hai, toh uska complement RE bhi nahi hoga, recursive toh bilkul nahi.3. False: CFL complement ke under closed nahi hai.4. True: L1 bar recursive hai => RE hai. RE ∪ RE = RE. Toh L1 bar ∪ L2 RE hai.
Isliye 1 and 4.Q 3.36 [2015 Set-2 : 1 Mark]
Question: Consider statements: 1. Complement of every Turing decidable is decidable. 2. There exists some language which is in NP but not decidable. 3. If L is in NP, L is decidable. Which is True?
(a) Only 2 (b) Only 3 (c) Only 1 and 2 (d) Only 1 and 3Answer: (d) Only 1 and 3Solution:1. True: Decidable languages complement ke under closed hai.2. False: Har NP language decidable hai. NP ⊆ PSPACE ⊆ Decidable. Aisa koi NP language nahi jo undecidable ho.3. True: Upar wale reason se hi.
Q 3.37
Question: X recursive, Y RE not recursive. W=X∪Y, V=X∩Y?
Answer: (d) W is RE not necessarily recursive, V is RE
Explain: RE ∪ RE = RE, RE ∩ RE = RE. Recursive subset hai RE ka. X=Φ le to W=Y jo recursive nahi. Isliye W ka recursive hona zaruri nahi.Q 3.38
Question: L1={|M halts on ε}, L2={|M has 2 states}
Answer: (b) L2 only decidable
Explain: L1 halting problem hai, undecidable but RE. L2 sirf syntax check hai, states gin sakte hai, Rice nahi lagta, decidable.Q 3.40
Question: CFG complement empty? DFA ∩ DFA empty?
Answer: DFA ∩ DFA empty decidable. CFG complement empty = L(G)=Σ_ jo undecidable.Q 3.44
Question: S1 All RE languages, S2 All C programs, S3 All languages over {0,1}, S4 All non-regular. Which uncountable?
Answer: (b) S3 and S4
Explain: RE aur C programs countable hai kyunki TM/programs countable. 2^Σ_ uncountable.Q 3.45
Question: L1 L(M)=Φ, L2 reaches q in 100 steps, L3 L(M) not recursive, L4 >=21 members
Answer: (b) L1,L3,L4 undecidable
Explain: L2 decidable – 100 steps me sirf 100 cells check. Baaki sab Rice se undecidable.Q 3.46 / 3.50d
Question: >2021 steps on all/some inputs?
Answer: Both decidable
Explain: 2021 steps me max 2021 cells. Finite inputs length ≤2021 hi check karne hai. Finite simulation.Q 3.47
Question: Which is NOT recursive? DFA Σ, PDA Σ, DFA ≥3 strings, DFA Φ
Answer: (b) PDA L=Σ*
Explain: PDA universality undecidable. Ye GATE me repeat hota hai.Q 3.51
Question: CNF 10 variables, w=a30b30c30, steps?
Answer: (c) 179
Explain: CNF me steps = 2n-1. n=30+30+30=90. To 89+90=179.Q 3.52
Question: TM decides L means?
Answer: (d) Accepts all in L and rejects complement, always halts.