• » When is the International Literacy Day observed every year? » 8th September
• » आयुष मंत्रालय ने व्यक्तिगत (अंतरराष्ट्रीय) श्रेणी में किसे 'प्रधानमंत्री योग पुरस्कार 2019' दिए जाने की घोषणा जून, 2019 में की- » अन्‍तोनिएता रोजी, इटली
• » वह अरब राष्ट्र जो की 'फाइनेंशियल एक्शन टास्क फोर्स' (FATF) की पूर्ण सदस्यता प्राप्त करने वाला पहला अरब देश जून, 2019 में बना- » सऊदी अरब
• » भारत ने किस देश को 3-1 से पराजित कर 'वुमेन एफआईएच सीरीज फाइनल हॉकी टूर्नामेंट' का खिताब 23 जून, 2019 को जीता? » जापान
• » भाजपा सांसद ओम बिरला राजस्थान के किस संसदीय क्षेत्र से सांसद चुने गए हैं; जिन्हें 17वीं लोकसभा का अध्यक्ष 19 जून, 2019 को चुना गया? » कोटा-बूंदी
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 2

THEORY OF COMPUTATION 2

# Q21. Nobody knows at present if P=NP. Consider the definition of L below L=(a^ib^jc^k|i>j>k} if the sum of subsets problem is in P L=(a^ib^jc^k|i,j,k all unequal} if P is not the same as NP a. L is regular and not finite b. We can tell the type of L after resolving the P=NP question c. L is recursive and not context-free d. L is context-free and not context-sensitive Q22. The regular expression 0*(10*)* denotes the same set as a. (0*1)0* b. 0 + (0 +10)* c.*0+1)*10(0+1)* d. none of the above Q23. The regular expression 0*(10*)* denotes the same set as a. (1*0)1* b. 0 + (0 +10)* c.*0+1)*10(0+1)* d. none of the above [GATE 2003] Q22. The regular expression 0*(10*)* denotes the same set as a. (0*1)1* b. 0 + (0 +10)* c.*0+1)*10(0+1)*+0*1* d. none of the above Q23. The regular expression (0+10)* denotes a. the set of all strings not containing two consecutive 0’s b. the set of all strings containing two consecutive 0’s c. the set of all strings with an even number of 0’s d. none of the above Q24. The regular expression (e +0+00)(1+10+100)* denotes a. the set of all strings not containing three consecutive 0’s b. the set of all strings containing three consecutive 0’s c. the set of all strings with an odd number of 0’s d. none of the above Q25. The regular expression (00+11+(01+10)(00+11)*(01+10))* denotes a. the set of all strings with an even number of 0s and an even number 0’s and an even number of 1’s b. the set of all strings over {0,1} c. the set of all strings with the 0’s and 1’s alternating d. none of the above Q26. If the strings of a language L 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 [GATE 2003] Q27. If the strings of a language L that is accepted by a turing machine 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 Q28. If the strings of a language L that are accepted by a multidimensional turing machine M 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 Q29. If the strings of a language L that are accepted by a 3 pebble machine M 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 Q30. If the strings of a language L that are accepted by a multitrack turing machine M 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 Q31. If the strings of a language L that are accepted by a nondeterminisitic, 56 pushdown tape machine M, 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 Q32. If the strings of a language L that are accepted by a nondeterministic 987 counter machine M, 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 Q33. If the strings of a language L that are accepted by a turing machine with 2-way infinite tape, 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 Q34. If the strings of a language L that are accepted by a 4567 headed nondeterministic turing machine,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 Q35. If the strings of a language L accepted by a turing machine, which has 1000 two way infinite tapes, 1000 symbols in the tape alphabet, 2000 input symbols, l345 dimensional tapes, 34567 heads, optional 345 pushdown tapes, 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 Q36. If the strings of a language L that are accepted by a machine which can keep 400 pebbles anywhere on its infinite input tape, but has no tape symbols, 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 Q37. If the strings of a language L that are accepted by a turing machine, with a whose tape alphabet is a singleton set, 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 Q38. If the strings of a language L={<M>|encoding of turing machine M}, 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 Q39. If the strings of a language L ={<M>|encoding of 45678 push down tape machines} 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 Q40. If the strings of a language L={<M>| M is an encoding of turing machines, pushdown automata, linear bounded automata, finite automata}, 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

## Tags

#

03 Jun, 2020, 03:39:30 AM