CurrentGK Papers GAT(Graduate Aptitude Test In Engineering) THEORY OF COMPUTATION 2

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

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

## Related Posts

Current Affairs