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^ki>j>k} if the sum of subsets problem is in P L=(a^ib^jc^ki,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 contextfree
d. L is contextfree and not contextsensitive
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 2way 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
