If you find this context important and usefull. We request to all visitors to sheare this with your friends on social networking channels.

THEORY OF COMPUTATION 3

# Q41. If the strings of a language L ={<M>| M is an encoding of turing machines that have more than 34567890 states}, can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true? a) L is necessarily finite b) L is regular but not necessarily finite c) L is context free but not necessarily regular d) L is recursive but not necessarily context free Q42. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is Sà aSb|SS|e Which of the following statements is true? a) G is not ambiguous b) There exist x and y in L(G) such that xy is not in L(G) c) There exist a deterministic push down automaton that accepts L(G) d) We can find a deterministic finite state automaton that accepts L(G) Q43. Let G=({S},{a,b,c},R,S) be a context-free grammar where the rule set is Sà aSa|bSb|c. Which of the following statements is true? a) G is ambiguous b) There exist x and y in L(G) such that xy is in L(G) c) There exist a deterministic push down automaton that accepts L(G) d) We can find a deterministic finite state automaton that accepts L(G) Q44. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is Sà aSb|SSSSSSSSSSS|e Which of the following statements is true? a) G is not ambiguous b) There exist x and y in L(G) such that xy is not in L(G) c) There exist a deterministic push down automaton that accepts L(G) d) We can find a deterministic finite state automaton that accepts L(G) Q45. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is Sà aSb|aaSbb|SS|e Which of the following statements is true? a) G is not ambiguous b) There exist x and y in L(G) such that xy is not in L(G) c) There exist a deterministic push down automaton that accepts L(G) d) We can find a deterministic finite state automaton that accepts L(G) Q46. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is Sà aaSbb|SS|e Which of the following statements is true? a) G is not ambiguous b) There exist x and y in L(G) such that xy is not in L(G) c) There exist a deterministic push down automaton that accepts L(G) d) We can find a deterministic finite state automaton that accepts L(G) Q47. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is Sà aaaSbbb|SS|e Which of the following statements is true? a) G is not ambiguous b) There exist x and y in L(G) such that xy is not in L(G) c) There exist a deterministic push down automaton that accepts L(G) d) We can find a deterministic finite state automaton that accepts L(G) Q48. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is Sà abSba|SS|e Which of the following statements is true? a) G is not ambiguous b) There exist x and y in L(G) such that xy is not in L(G) c) There exist a deterministic push down automaton that accepts L(G) d) We can find a deterministic finite state automaton that accepts L(G) Q49. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is Sà aaabaaaSbbbabbb|SS|e Which of the following statements is true? a) G is not ambiguous b) There exist x and y in L(G) such that xy is not in L(G) c) There exist a deterministic push down automaton that accepts L(G) d) We can find a deterministic finite state automaton that accepts L(G) Q50. Choose the correct statement for the language L={a^nb^n|n>=0} a) L is inherently ambiguous b) L is deterministic context-free c) L is regular d) There exists a deterministic two way finite automata accepting L Q51. Choose the correct statement for the language L={a^100nb^100n|n>=0} a) L is inherently ambiguous b) L is deterministic context-free c) L is regular d) There exists a deterministic two way finite automata accepting L Q52. Choose the correct statement for the language L={(aaabaaa)^1000n(bbbbbbb)^34567n|n>=0} a) L is inherently ambiguous b) L is deterministic context-free c) L is regular d) There exists a deterministic two way finite automata accepting L Q53. Choose the correct statement for the language L={"("^n " )" ^n|n>=0} a) L is inherently ambiguous b) L is deterministic context-free c) L is regular d) There exists a deterministic two way finite automata accepting L Q54. Choose the correct statement for the language L={(begin)^n(end)^n|n>=0} a) L is inherently ambiguous b) L is deterministic context-free c) L is regular d) There exists a deterministic two way finite automata accepting L Q55. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is Sà aSb|SS|e Which of the following statements is true? a) G is not ambiguous b) There exist x and y in L(G) such that xy is not in L(G) c) L(G) is the set of all strings of balanced parenthesis with a as the opening parenthesis and b as the closing parenthesis. d) We can find a deterministic finite state automaton that accepts L(G) Q56. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^-1 be also polynomial time computable. Which of the following CANNOT be true? a) L1 e P and L2 finite b) L1e NP and L2e P c) L1 is undecidable and L2 is decidable d) L1 is recursively enumerable and L2 is recursive Q57. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^-1 be also polynomial time computable. Which of the following CANNOT be true? a) L1 e P and L2 finite b) L1e NP and L2e P-SPACE c) L1 is undecidable and L2 is decidable d) L1 is recursively enumerable and L2 is context-sensitive Q58. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^-1 be also polynomial time computable. Which of the following CANNOT be true? a) L1 e P and L2 regular b) L1e NP and L2e P c) L1 is undecidable and L2 is decidable d) L1 is context-sensitive and L2 is recursive Q59. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^-1 be also polynomial time computable. Which of the following CANNOT be true? a) L1 e P-SPACE and L2 e DSPACE(n^1000) b) L1e NP and L2e DTIME(2^1000n) c) L1 is undecidable and L2 is decidable d) L1 is recursively enumerable and L2 is accepted by a 2PDA Q60. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a polynomial time computable bijection such that (Ñ x)[xe L2]. Further, let f^-1 be also polynomial time computable. Which of the following CANNOT be true? a) L1 e P and L2 is accepted by a 2NFA b) L1e NP and L2is accepted by a linear bounded automata c) L1 is undecidable and L2 is decidable d) L1 is recursively enumerable and L2 is accepted by a turing machine that halts on all inputs

## Tags

#

Current Affairs
♦ PRAGATI प्‍लेटफार्म एक _____________ स्तरीय प्रणाली है। » 3
♦ अंतर्राष्ट्रीय शिक्षा दिवस कब मनाया गया? » 24 जनवरी
♦ अंतर्राष्ट्रीय शिक्षा दिवस कब घोषित किया गया था? » 3 दिसंबर, 2018
♦ भारत-पाकिस्तान युद्ध कब स्थापित किया गया था? » 1965
♦ शिक्षा का अधिकार भारतीय संविधान के ____________ में डाला गया था » अनुच्छेद 21-ए
♦ ऑपरेशन शरद हवा कब खत्म हुआ? » 27 जनवरी, 2021
♦ शिक्षा का अधिकार ____________ आयु वर्ग के बच्चों के लिए एक बुनियादी अधिकार है। » 6 से 14
♦ मानव अधिकारों की सार्वभौमिक घोषणा के ____________ में शिक्षा का अधिकार शामिल है। » अनुच्छेद 26
♦ पेरियार टाइगर रिजर्व कहाँ स्थित है? » केरला
♦ नवंबर 2020 तक, भारत की स्थापित सौर ऊर्जा क्षमता ____________ है » 36.9 GW