TOC mCQ Two

1.	Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE? P3 is decidable if P1 is reducible to P3 P3 is undecidable if P3 is reducible to P2 P3 is undecidable if P2 is reducible to P3 P3 is decidable if P3 is reducible to P2’s complement
2.	Consider three problems P1, P2 and P3. It is known that P1 has polynomial time solution and P2 is NP-complete and P3 is in NP. Which one of the following is true. P3 has polynomial time solution if P1 is polynomial time reducible to P3 P3 is NP complete if P3 is polynomial time reducible to P2 P3 is NP complete if P2 is reducible to P3 P3 has polynomial time complexity and P3 is reducible to P2
3.	Consider the FSA M The language recognized by M is {w ∊ {a, b}* | every a in w is followed by exactly two b’s} {w ∊ {a, b}* | every a in w is followed by atleast two b’s} {w ∊ {a, b}* |w contains the substring ‘abb’} {w ∊ {a, b}* |w does not contain ‘aa’ as substring}
4.	Let Nf and Np denote the classes of languages accepted by nondeterministic FSA and nondeterministic PDA, respectively. Let Df and Dp denote the classes of languages accepted by deterministic FSA and PDA respectively. Which of the following is TRUE? Some of these questions have appeared in GATE examinations. Df ⊂ Nf Dp ⊂ Np Df ⊂ Nf Dp = Np Df = Nf Dp ⊂ Np Df = Nf Dp = Np
5.	Consider the languages L1 = {anbncm|n, m > 0} and L2 = {anbmcm|n, m > 0} Which one of the following statements is false? L1 ∩ L2 is a CFL L1 ∪ L2 is a CFL L1 ∪ L2 is inherently ambiguous L1 ∩ L2 is a CSL
6.	Consider the languages L1 = {anbmcndp|n, m, p > 0} and L2 = {anbmcpdm|n, m, p> 0} Which one of the following statements is false? L1 ∩ L2 is a CFL L1 ∪ L2 is a CFL L1 ∪ L2 is inherently ambiguous L1 ∩ L2 is a CSL
7.	Consider the languages L1 = {anbmcmdn|n, m > 0} and L2 = {anbncmdm|n, m > 0} Which one of the following statements is false? L1 ∪ L2 is a CFL L1 ∩ L2 is a CFL L1 and L2 are CFL L1 ∩ L2 is a CSL
8.	Let L and be a language and its complement. Which one of the following possibilities will not hold? L and are recursive L is recursively enumerable but not recursive is not recursively enumerable L and are not recursively enumerable L and are recursively enumerable but not recursive
9.	Let L1 be a recursive language and let L2 be a recursively enumerable language which is not recursive. Which one of the following is TRUE? is recursive, is recursively enumerable. is recursive, is not recursively enumerable. and are recursively enumerable. is recursively enumerable and is recursive.
10.	Consider the languages L1 = {wwR|w ∊ {0,1}*} L2 = {wcwR|w ∊ {0,1}*} L3 = {ww|w ∊ {0,1}*} Which one of the following is TRUE? L1 is deterministic CFL L2 is deterministic CFL L3 is a CFL but not a deterministic CFL L3 is deterministic CFL
11.	Let S be a NP–complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which one of the following statements is TRUE? R is NP complete R is NP hard Q is NP complete Q is NP hard
12.	L1 = {an + m bn cm|n, m ≥ 0} L2 = {an + m bn + m cm|n, m ≥ 0} L3 = {an + m bn + m cm + n|n, m ≥ 0} Which of these languages are not CF. L1 only L3 only L1 and L2 L2 and L3
13.	If s is a string over (0+1)* then let m0 (s) denote the number of 0’s in s and n1 (s) the number of 1’s in s. Which one of the following languages is not regular? L = {s ∊ (0+1)*|n0(s) is a 3-digit prime} L = {s ∊ (0+1)*|for every prefix s′ of s, |n0 (s′) − n1(s′)| ≤ 2} L = {s ∊ (0+1)*‖n0(s) − n1(s)| ≤ 4} L = {s ∊ (0+1)*|n0(s) mod 7 = n1(s) mod 5 = 0}
14.	For s ∊ (0+1)*let d(s) denote the decimal value of s (eg. D(|0|) = 5). Let L = {s ∊ (0+1)*|d(s) mod 5 = 2 and d(s) mod 7 ≠ 4} Which one of the following statements is TRUE? L is recursively enumerable but not recursive L is recursive, but not context-free L is context-free, but not regular L is regular
15.	Let FHAM be the problem of finding a Hamiltonian cycle in a graph G and DHAM be the problem of determining if a Hamiltonial cycle exists in a graph. Which one of the following is TRUE? Both FHAM and DHAM are NP-hard FHAM is NP hard, but DHAM is not DHAM is NP hard, but FHAM is not Neither FHAM nor DHAM is NP hard
16.	Consider the following statements about the context-free grammar G = {S → SS, S → ab, S → ba, S → c} G is ambiguous G produces all strings with equal number of a’s and b’s G can be accepted by a deterministic PDA Which combination below expresses all the true statements about G? I only I and III only II and III only I, II and III
17.	Let L1 be a regular language and L2 a deterministic CFL. L3 is recursively enumerable but not recursive. Which one of the following statement is FALSE? L1 ∩ L2 is a DCFL L3 ∩ L1 is recursive L1 ∪ L2 is context-free L1 ∩ L2 ∩ L3 is recursively enumerable
18.	Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting the language is 3 5 8 9
19.	Which one of the following grammars generates the language L = {aibj|i ≠ j}. S → AC|CB C → aCb|a|b A → aA|ε B → Bb|ε S → aS|Sb|a|b S → AC|CB C → aCb|ε A → aA|ε B → Bb|ε S → AC|CB C → aCb|ε A → aA|a B → bB|b
20.	In the above correct grammar what is the minimum length of the derivation (number of steps starting from S) to generate the string a1 bm with l ≠ m? max(l, m) + 2 l + m + 2 l + m + 3 max(l, m) + 3
21.	Consider S → SS|a. What is the number of different derivation trees for aaaaa 3 5 7 14
22.	Which one of the following grammar generates L = {ai bj ck|i ≠ k, i, j, k ≥ 1} S → AC|CB A → aA|a B → Bc|c C → aCc|bD|b D → bD|b S → aS|aA A → bA|bB B → cB|c S → AB A → aAb|ab B → bBc|bc S → AC|CB A → aA|ε B → Bc|ε C → aCc|ε|bD D → bD|b|ε
23.	A minimum state deterministic automaton accepting the language L = {w|w ∊ {0,1}*, the number of 0’s and 1’s in w are divisible by 3 and 5 respectively} has 15 states 11 states 10 states 9 states
24.	The language L = {0i21i / i ≥ 0} over the alphabet {0, 1, 2} is not recursive is recursive and is a deterministic CFL is a regular language is not a deterministic CFL but a CFL
25.	Which of the following languages is regular? {wwR|w ∊ {0, 1}+} {wwRx|w, x ∊ {0, 1}+} {w x w R|w, x ∊ {0, 1}+} {xwwR|w, x ∊ {0, 1}+}
26.	Let Σ = {0, 1}, L1 = Σ* and L2 = {0n 1n|n ≥ 1} then the languages L1 ∪ L2 and L2 are respectively regular, regular regular, not regular not regular, regular not regular, not regular
27.	Which of the following statements is false? The halting problem for Turing machines is undecidable determining whether a context-free grammar is ambiguous is un-decidable given two arbitrary context-free grammar, G1 and G2, it is undecidable with L(G1) = L(G2) given two regular grammars G1 and G2, it is undecidable whether L(G1) = L(G2)
28.	Two of the following four regular expressions are equivalent. Which two? (00)* (0 + ε) (00)* 0* 0(00)* (i) and (ii) (ii) and (iii) (i) and (iii) (iii) and (iv)
29.	Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true? L = {x|x has an equal number of a’s and b’s } is regular L = {an bn | n ≥ 1} is regular L = {am bn | m, n ≥ 1} is regular L = {x|x has more a’s than b’s} is regular
30.	Define for a CFL L, init (L) = {u | uv ∊ L for some v ∊ {0, 1}*}. In other words init (L) is the set of prefixes of L. Let L = {w|w ∊ {0, 1}+, w has equal number of 0’s and 1’s}. Then init (L) is the set of all binary strings with unequal number of 0’s and 1’s the set of all binary stings including ε the set of all binary strings with exactly one more 0 than the number of 1’s or one more 1 than the number of 0’s. none of the above
31.	If L1 and L2 are CFL and R a regular set, one of the languages below is not necessarily a CFL. Which one? L1L2 L1 ∪ L2 L1 ∩ L2 L1 ∩ R
32.	The grammar whose productions are 〈stmt〉 → if 〈id〉 then 〈stmt〉 〈stmt〉 → if 〈id〉 then 〈stmt〉 else 〈stmt〉 〈stmt〉 → 〈id〉 := 〈id〉 〈id〉 → a|b|c|d|f is ambiguous because the sentence if a then if b then c := d has more than one derivation trees the leftmost and rightmost derivation of the sentence if a then if b then c := d give rise to different parse trees the sentence if a then if b then c := d else c := f has more than two parse trees the sentence if a then if b then c := d else c := f has two parse trees
33.	Which one of the following regular expressions over {0, 1} denotes the set of all strings not containing 100 as a substring? 0*(11*0)* 0*1010* 0*1*01 0*(10 + 1)*
34.	Which one of the following is not decidable? given a Turing machine M, a string s, and an integer k, M accepts s with k steps equivalence of two given Turing machines language accepted by a given DFSA is nonempty language generated by a CFG is nonempty
35.	Which of the following languages over {a, b, c} is accepted by a deterministic PDA? {wbwR|w ∊ {a, c}*} {wwR|w ∊ {a, b, c}*} {anbncn|n ≥ 1} {w|w is a palindrome over {a, b, c}}
36.	Which of the following instances of the post correspondence problem has a viable sequence (a solution)? {(b, bb), (bb, bab), (bab, abb), (abb, babb)} {(ab, aba), (baa, aa), (aba, baa)} {(ab, abb), (ba, aaa), (aa, a)} none of the above
37.	It is undecidable, whether an arbitrary TM has 15 states an arbitrary TM halts after 10 steps an arbitrary TM ever prints a specific letter an arbitrary TM accepts a string w in 5 steps
38.	Let r = 1(1+0)*, s = 11*0 and t = 1*0 be three regular expressions and R, S, T the regular sets corresponding to them. Which of the following is true? S ⊂ R R ⊂ S T ⊂ S R ⊂ T
39.	Which one of the following is the strongest correct statement about a finite language L over a finite alphabet Σ? L is undecidable L is recursive L is a CSL L is a regular set
40.	Which of the following statements is TRUE? infinite union of regular sets is regular infinite union of finite sets is regular finite union of finite sets is regular complement of a finite set need not be regular Answers 1. c 2. c 3. b 4. c 5. a 6. a 7. b 8. d 9. b 10. b 11. b 12. d 13. c 14. d 15. a 16. b 17. b 18. d 19. a 20. a 21. d 22. a 23. a 24. b 25. c 26. b 27. d 28. c 29. c 30. b 31. c 32. d 33. d 34. b 35. a 36. c 37. c 38. a 39. d 40. c