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
