*QUESTION BANK II*

*THEORY OF COMPUTATION*

Q1. The language {a^i b^j c^k| i=j or j=k} is

A. regular

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q2. The language {a^i b^j c^k|k=min(i,j)} is

A. regular

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q3. The language {a^i b^j c^k| k= max(i,j)} os

A. regular

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q4. The language {a^n b^n c^i| i<>n} is

A. regular

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q5. The language {a^i b^j c^k| i<=k<=2j} is

A. regular

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q6. The language {a^i b^j c^k|i<j<k} is

A. regular

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q7. The language {a^i b^j c^k|i+j>=k} is

A. regular

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q8. The langugae {a^i b^j c^k|k<=i or k<=j} is

A. regular

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q9.{a^i b^i c^j d^j|i,j>=1} is

A. regular

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q10. The language {a^i b^i c^j d^2 e^3i|i,j>=1} is

A. regular

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q11. The language {w| w has equal number of a's, b's and c's } is

A. regular

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q12. The language {0^n1^n|n>=1} U {0^n 1^2n|n>=1} is

A. regular

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q13. The language {0^n1^n|n>=1} U {0^n 1^2n|n>=1} is

A. regular

B. deterministic context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q14. The language {0^n1^n|n>=1} U {0^n 1^2n|n>=1} is

A. regular

B. context-free but not deterministic context free

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q15. {0^i 1^ja2^i|j>=i} U {0^i 1^jb2^i|j>=i} is

A. regular

B. context-free but not deterministic context free

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q16. {0^i 1^ja2^i|j>=i} U {0^i 1^jb2^i|j>=i} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q 17. The language {a^n!|n>=1} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q18. The language {a^ceil(log2n)|n>=1} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q19. {0^n 1^n^2|n>=1} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q20. The langugae {a^p|p prime} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q21. The language {0^p|p not prime} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q22. 0^2^n|n>=1} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q23. The language {a^i b^j c^j|j>=i} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q24. The language {a^i b^i c^i|n>=1} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q25. The language {a^i b^j c^k|i,j,k>=1} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q26. The language {a^i b^j c^k | i<>j or j<>k or k<>i} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q27. The language {w| w in binary is a prime} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q28. {0^n 1^n|n>=1} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q29. The languge {0^1 1^j|gcd(i,j)=1} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q30. {w| w has equal number of a's and b's } is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q31.The language {ww| w a string over the alpahabet} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q32. The set of all palidromes over some alphabet is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q33. The languge {a^i b^j c^k d^l| i=0 or j=k=l} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q34. The language {w| w in {0,1}* and w does not have three consecutive 0's} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q35. The language {xwxR|x,w in (0+1)+} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q36. The language {xxRw|s,w in (0+1)+} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q37.The language {w| w is the set of all balanced parenthesis} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q38. The language {w| w is a well-formed regular expression over some alphabet} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q39. The language {w| strings not of the form xx, x in (0+1)*} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q40. The languge {w| w is not of the form a^n b^n c^n } is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q41.The set {0,1,#}+-{b1#b2#...#bn|n>=1} where bi is the binary representation of i is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q42. The language {a^i b^j c^k d^l| i= j or j=k} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q43. The language (a+b)*-{(a^nb^n)^n|n>=1} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q44. The language {wwRw| w in (a+b)+} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q45. The languge {bi#b(i+1)|bi is in binary } is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q46. The languge {wxw| w, x in (c+d)*} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q47. The languge (a+b)*-{(a^nb^n)^n|n>=1} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q48. The languge {a^n b^nc^i| i <> n} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q49. The language {a^n!|n>=1} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q50. The languge {w| w has equal number of a's,b's, c's or equal number a's, b's and d's} is

A. regular

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q51. The language {a^i b^j c^k| i=j or j=k} is

A. regular but not finite

B. deterministic context-free but not regular

C. context-sensitive but not regular

D.type-0 but not context-sensitive

Choose your answer by clicking below.

Q52. The language {a^i b^j c^k|k=min(i,j)} is

A. regular but not finite

B. context-free but deterministic context free

C. context-sensitive but not deterministic context-free

D.recursive but not context-sensitive

Choose your answer by clicking below.

Q53. The language {a^i b^j c^k| k= max(i,j)} os

A. regular but not context-free

B. context-free but not regular

C. context-sensitive but not context-free

D.recursive but not context-sensitive

Choose your answer by clicking below.

Q54. The language {a^n b^n c^i| i<>n} is

A. regular but not finite

B. context-free but not regular

C. context-sensitive but not deterministic context-free

D.recursive but not context-sensitive

Choose your answer by clicking below.

Q55. The language {a^i b^j c^k| i<=k<=2j} is

A. regular but not finite

B. context-free but not deterministic context-free

C. context-sensitive but not context-free

D.recursive but not context-sensitive

Choose your answer by clicking below.

Q56. The language {a^i b^j c^k|i<j<k} is

A. regular but not finite

B. context-free but not regular

C. context-sensitive but not context-free

D.recursive or type-0 but not context-sensitive

Choose your answer by clicking below.

Q57. The language {a^i b^j c^k|i+j>=k} is

A. regular but not finite

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q58. The langugae {a^i b^j c^k|k<=i or k<=j} is

A. regular but not finite

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q59.{a^i b^i c^j d^j|i,j>=1} is

A. regular but not finite

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q60. The language {a^i b^i c^j d^2 e^3i|i,j>=1} is

A. regular and finite

B. context-free but not regular

C. context-sensitive but not context-free

D.recursive but not context-sensitive

Choose your answer by clicking below.

Q61. The language {w| w has equal number of a's, b's and c's } is

A. regular but not finite

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q62. The language {0^n1^n|n>=1} U {0^n 1^2n|n>=1} is

A. regular but not finite

B. context-free but not regular

C. context-sensitive but not context-free

D.recursive but not context-sensitive

Choose your answer by clicking below.

Q63. The language {0^n1^n|n>=1} U {0^n 1^2n|n>=1} is

A. regular and finite

B. deterministic context-free but not regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q64. The language {0^n1^n|n>=1} U {0^n 1^2n|n>=1} is

A. regular but not finite

B. context-free but not deterministic context free

C. context-sensitive but not context-free

D.type-0or recursive but not context-sensitive

Choose your answer by clicking below.

Q65. {0^i 1^ja2^i|j>=i} U {0^i 1^jb2^i|j>=i} is

A. regular and not finite

B. context-free but not deterministic context free

C. context-sensitive but not context-free

D.type-0 but nor recursive

Choose your answer by clicking below.

Q66. {0^i 1^ja2^i|j>=i} U {0^i 1^jb2^i|j>=i} is

A. regular and infinite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q 67. The language {a^n!|n>=1} is

A. regular and finite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q68. The language {a^ceil(log2n)|n>=1} is

A. regular and also deterministic context free

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q69. {0^n 1^n^2|n>=1} is

A. regular and not finite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q70. The langugae {a^p|p prime} is

A. regular and not finite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or deterministic context free

Choose your answer by clicking below.

Q71. The language {0^p|p not prime} is

A. regular and finite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q72. 0^2^n|n>=1} is

A. regular and not finite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q73. The language {a^i b^j c^j|j>=i} is

A. regular and finite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or deterministic context-free

Choose your answer by clicking below.

Q74. The language {a^i b^i c^i|n>=1} is

A. regular and not deterministic context free

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q75. The language {a^i b^j c^k|i,j,k>=1} is

A. regular and infinite

B. context-free but regular

C. context-sensitive but not context-free

D.recursive but not context-sensitive

Choose your answer by clicking below.

Q76. The language {a^i b^j c^k | i<>j or j<>k or k<>i} is

A. regular and infinite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q77. The language {w| w in binary is a prime} is

A. regular and not finite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q78. {0^n 1^n|n>=1} is

A. regular and not finite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q79. The languge {0^1 1^j|gcd(i,j)=1} is

A. regular and not infinite

B. context-free but regular

C. context-sensitive but not context-free

D.recursive but not context-sensitive

Choose your answer by clicking below.

Q80. {w| w has equal number of a's and b's } is

A. regular and infinite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or deterministic context-free

Choose your answer by clicking below.

Q81.The language {ww| w a string over the alpahabet} is

A. regular and infinite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q82. The set of all palidromes over some alphabet is

A. regular and finite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or deterministic context free

Choose your answer by clicking below.

Q83. The languge {a^i b^j c^k d^l| i=0 or j=k=l} is

A. regular and finite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q84. The language {w| w in {0,1}* and w does not have three consecutive 0's} is

A. regular and infinite

B. context-free but not regular and not determinitstic context free

C. context-sensitive but not context-free

D.type-0 but not context-sensitive and not recursive

Choose your answer by clicking below.

Q85. The language {xwxR|x,w in (0+1)+} is

A. regular and infinite

B. context-free but regular and not deterministic context-free

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q86. The language {xxRw|s,w in (0+1)+} is

A. regular and infinite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q87.The language {w| w is the set of all balanced parenthesis} is

A. regular and finite

B. context-free but not regular and is infinite

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q88. The language {w| w is a well-formed regular expression over some alphabet} is

A. regular and infinite

B. context-free but regular

C. context-sensitive but not context-free

D.recursive but not context-sensitive

Choose your answer by clicking below.

Q89. The language {w| strings not of the form xx, x in (0+1)*} is

A. regular and infinite

B. context-free but not regular or deterministic context-free

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q90. The languge {w| w is not of the form a^n b^n c^n } is

A. regular and infinite

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q91.The set {0,1,#}+-{b1#b2#...#bn|n>=1} where bi is the binary representation of i is

A. regular and infinite

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q92. The language {a^i b^j c^k d^l| i= j or j=k} is

A. regular and infinite

B. context-free but not regular or deterministic context free

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q93. The language (a+b)*-{(a^nb^n)^n|n>=1} is

A. regular and finite

B. context-free but not regular or deterministic context-free

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q94. The language {wwRw| w in (a+b)+} is

A. regular and finite

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q95. The languge {bi#b(i+1)|bi is in binary } is

A. regular and finite

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q96. The languge {wxw| w, x in (c+d)*} is

A. regular and infinite

B. context-free but not regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q97. The languge (a+b)*-{(a^nb^n)^n|n>=1} is

A. regular and infinite

B. context-free but not regular or deterministic context-free

C. context-sensitive but not context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q98. The languge {a^n b^nc^i| i <> n} is

A. regular and finite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q99. The language {a^n!|n>=1} is

A. regular and infinite

B. context-free but not regular

C. context-sensitive but not context-free or deterministic context-free

D.type-0 but not context-sensitive or recursive

Choose your answer by clicking below.

Q100. The languge {w| w has equal number of a's,b's, c's or equal number a's, b's and d's} is

A. regular and infinite

B. context-free but regular

C. context-sensitive but not context-free

D.type-0 or recursive but not context-sensitive

Choose your answer by clicking below.

Q101. The language {a^mb^nc^(m+n)|m,n>=1} is

A. regular

B.context-free but not regular

C. context-sensitive but not context-free

D. type0 but not context sensitive

Choose your answer by clicking below.

[GATE 2004]

Q102. The language {a0^n 1^n|n>=1} U{b0^n 1^2n|n>=1} is

A. regular

B.context-free but not regular

C. context-sensitive but not context-free

D. type0 but not context sensitive

Choose your answer by clicking below.

Q104. The language {a0^n 1^n|n>=1} U{b0^n 1^2n|n>=1} is

A. regular

B.deterministic context-free but not regular

C. context-sensitive but not context-free

D. type0 but not context sensitive

Choose your answer by clicking below.

Q105. The language {a0^n 1^n|n>=1} U{b0^n 1^2n|n>=1}U {c0^n 1^4n

|n>1} is

A. regular

B.context-free but not regular

C. context-sensitive but not context-free

D. type0 but not context sensitive

Choose your answer by clicking below.

Q106. The language {a0^n 1^n|n>=1} U{b0^n 1^2n|n>=1}U {0^n1^89n|n>=1} is

A. regular

B.deterministic context-free but not regular

C. context-sensitive but not context-free

D. type0 but not context sensitive

Choose your answer by clicking below.

Q107. The language {awwRbxxRcyyR|x,y,z in {0,1}*}is

A. regular

B.context-free but not regular

C. context-sensitive but not context-free

D. type0 but not context sensitive

Choose your answer by clicking below.

Q108. The language {awwRbxxRcyyRdwwR|x,y,w in (0+1)*}is

A. regular

B.deterministic context-free but not regular

C. context-sensitive but not context-free

D. type0 but not context sensitive

Choose your answer by clicking below.

Q109. A language denoted by a semi-extended regular expression which is regular expression with the additional operation of intersection of regular expressions is

A. regular

B.context-free but not regular

C. context-sensitive but not context-free

D. type0 but not context sensitive

Choose your answer by clicking below.

Q110. A language denoted by extended regular expressions which is regular expressions with the operations of intersection and complementation is

A. regular

B.deterministic context-free but not regular

C. context-sensitive but not context-free

D. type0 but not context sensitive

Choose your answer by clicking below.

Q111. The language {w#wR#|w in (0+1)+} U{wwR|w in ()+1+2)*} is

A. regular

B.context-free but not regular

C. context-sensitive but not context-free

D. type0 but not context sensitive

Choose your answer by clicking below.

Q112. The language {a0^n 1^n 2^n|n>=1} U{b0^n 1^2n|n>=1}U {0^n1^89n|n>=1} is

A. regular

B.deterministic context-free but not regular

C. context-sensitive but not context-free

D. type0 but not context sensitive

Choose your answer by clicking below.

Q113. Choose the false statement. The regular sets are closed under

A. intersection

B. union

C. complement

D. inverse substitution

Choose your answer by clicking below.

Q114. Choose the false statement. The regular sets are closed under

A. MAX

B. MIN

C. INIT

D. inverse substitution

Choose your answer by clicking below.

Q115. Choose the false statement. The regular sets are closed under

A. CYCLE

B. INTERLEAVING

C. REVERSAL

D. inverse substitution

Choose your answer by clicking below.

Q116. Choose the false statement. The regular sets are closed under

A. intersection

B. SUBSTITUTION

C. complement

D. inverse substitution

Choose your answer by clicking below.

Q117. Choose the false statement. The regular sets are closed under

A. quotient with a regular set

B. quotient with a context free language

C. quotient with a context-free language

D. inverse substitution

Choose your answer by clicking below.

Q118. Choose the false statement. The regular sets are closed under

A. quotient with a recusive set

B. quotient with a r.e. language

C. quotient with any formal language

D. inverse substitution

Choose your answer by clicking below.

Q119. Choose the false statement. The regular sets are closed under

A. Kleene closure

B. quotient with a context free language

C. quotient with a context-free language

D. inverse substitution

Choose your answer by clicking below.

Q120. Choose the false statement. Let L be any formal language

A. L* is regular

B. L* is not necessaily regular

C. L* is context-free and not regular

D. L* is r.e. and not recursive

Choose your answer by clicking below.

Q121. Choose the false statement. The regular sets are closed under

A. homomorphism

B. quotient with a deterministic context free language

C. inverse homomorphism

D. inverse substitution

Choose your answer by clicking below.

Q122. Let L be a formal lanaugae. The set Lhalf is obtained by taking the first halves of strings in L. Choose the true statement

A. If L is regular then Lhalf is regular

B. If L is regular then Lhalf is not regular

C. If L is a cfl then Lhalf is a cfl

D. If L is a csl then Lhalf is a cfl

Choose your answer by clicking below.

Q123. The cfls are not closed under

A. substitution, homomorphism, union

B. union, conctenation, Kleene closure

C.homomorphism, inverse homomorphism, intersection with a regular set

D. inverse substitution

Choose your answer by clicking below.

Q124. The cfls are not closed under

A. MIN,MAX

B. union,Kleene closure, INIT

C. CYCLE

D. reversal

Choose your answer by clicking below.

Q125. The cfls are not closed under

A. half--the language formed by taking the first halves of strings of a cfl

B. gsm mappings

C. Kleene closure, intersection with a regular set

D. complement

Choose your answer by clicking below.

Q126. The complements of the cfls {a^nb^nc^n|n>=1} and {ww|w in (0+1)+}are

A. Regular, Regular

B. both cfls

C. both csls but not cfls

D. CFL and regular

Choose your answer by clicking below.

Q127. The cls are not closed under

A. union

B. intersection

C. substitution

D. quotient with a regular set

Choose your answer by clicking below.

Q128. The recursive sets are not closed under

A. complementation

B. union

C. intersection

D. substitution

Choose your answer by clicking below.

Q130. The recursivse sets are not closed under

A. homomorphism

B. e-free homomorphism

C. intersection

D. positive Kleene closure

Choose your answer by clicking below.

Q131. The r.e. sets are not closed under

A. union

B. intersection

C. complement

D. reversal

Choose your answer by clicking below.

Q132. The r.e. sets are not closed under

A. intersection

B. substitution

C. CYCLE

D. complement

Choose your answer by clicking below.

Q133. The complement of a r.e. set L that is not recursive

A.may be recursive

B. is always r.e.

C. is not r.e.

D. may be a csl

Choose your answer by clicking below.

Q134. Choose the false statement. The cfls are not closed under intersection. The intersection of two cfls may be

A. regular

B. cfl

C.csl

D. not r.e.

Choose your answer by clicking below.

Q135. The DCFLs are not closed under(choose the false statement)

A. union, Kleene closure, homomorphism

B. positive Kleene closure, reversal

C. concatenation, INIT

D.complementation

Choose your answer by clicking below.

Q136. The DCFLs are not clsoed under(choose the false statement)

A. union, substitution

B. MIN,MAX

C. intersection

D. inverse substitution

Choose your answer by clicking below.

Q137. Choose the false statement. The following languages are closed under reversal

A. Regular

B. cfls

C.dcfls

D. recursive sets

Choose your answer by clicking below.

Q138. Choose the false statement. The following languages are closed under reversal

A. r.e. sets

B. csls

C.dcfls

D. recursive sets

Choose your answer by clicking below.

Q139. Choose the false statement. The following languages are closed under complement

A. regular sets

B. dcfls

C. cfls

D. recursive sets

Choose your answer by clicking below.

Q140. Choose the false statement. The following languages are closed under complement

A. regualar sets

B. r.e. sets

C. dcfls

D. recursive sets

Choose your answer by clicking below.

Q139. Choose the false statement. The following languages are closed under complement

A. regular sets

B. dcfls

C. finite sets

D. recursive sets

Choose your answer by clicking below.

Q140. The following languages are closed under substitution(choose the false statement)

A. regular sets

B. dcfls

C. cfls

D. r.e. sets

Choose your answer by clicking below.

Q141. The following languages are closed under substitution(choose the false statement)

A. regular sets

B. cfls

C. csls

D. recursive sets

Choose your answer by clicking below.

Q142. Choose the false statement. The reversal of a dcfl L is

a. never r.e.

b. is always r.e.

c. is always a cfl

d. is always a csl

Choose your answer by clicking below.

Q143. Choose the false statement. The reversal of a dcfl L is

a. always a dclf

b. always a cfl

c. always a recursive set

d. always a r.e. set

Choose your answer by clicking below.

Q144. Choose the false statement. The union of two dcfls is

a. never r.e.

b. is always r.e.

c. is always a cfl

d. is always a csl

Choose your answer by clicking below.

Q145. Choose the false statement. The union of two dcfls is

a. always a dclf

b. always a cfl

c. always a recursive set

d. always a r.e. set

Choose your answer by clicking below.

Q146. The intersection of two cfls can simulate an arbitrary turing machine computation, and this can be used to show some problems are undecidable. The intersection of two cfls is (choose the false statement)

a. never regular

b. never a cfl

c. never a csl

d. always not r.e.

Choose your answer by clicking below.

Q147. The intersection of two dcfls can simulate an arbitrary turing machine computation, and this can be used to show some problems are undecidable. The intersection of two dcfls is (choose the false statement)

a. never regular

b. never a cfl

c. never a csl

d. always not r.e.

Choose your answer by clicking below.

Q148. The intersection of two csls can simulate an arbitrary turing machine computation, and this can be used to show some problems are undecidable. The intersection of two csls is (choose the false statement)

a. never a recursive set

b. never a cfl

c. never a csl

d. always not r.e.

Choose your answer by clicking below.

Q149. It is not known at present if the csls are closed under complement. The complement of a csl(choose the false statement) is

a. never a cfl

b. never a csl

c. never a recursive set

d. may be a set which is not r.e.

Choose your answer by clicking below.

Q150. The shuffle of languages L1 and L2 is obtained by shuffling the words of L1 with that of L2. Choose the false statement

a. the shuffle of two regular sets is regular

b. the shuffle of two cfls is a cfl

c. the shuffle of a cfl and a regular set is a cfl

d. the shuffle of a regular set and a cfl may be regular

Choose your answer by clicking below.

Q151. The following problems are decidable

a. whether a turing machine has at least three states

b. whether a turing machine will ever halt

c. whether a turing machine will ever print a symbol

d. whether a turing machine will ever enter a designated state

Choose your answer by clicking below.

Q152. The following problems are decidable

a. whether a turing machine ever leaves a particular cell it it scanning

b.whether a turing machine started on blank tape will ever halt

c. whether a turing machine accepts at least two strings

d. whether a turing machine accepts a finite set

Choose your answer by clicking below.

Q153. The following problems are decidable

a. whether the tape alphabet has at least two symbols

b. whether a turing machine with 12 tapes will accept an infinite set

c. for ever string w the turing machine accepts it also accepts wR.

d. whether a turing machine will ever print three consecutive 1's

Choose your answer by clicking below.

Q154. Let L1={<M>| M is the encoding of a finite auotmaton} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a turing machine}. The following problems are decidable(choose the false statement)

a. Whether L1 contains w

b. Whether L1 is empty

c. Whether L1 is infinite

d. Whether L2=L1

Choose your answer by clicking below.

Q155. Let L1={<M>| M is the encoding of a finite auotmaton} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a turing machine}. The following problems are decidable(choose the false statement)

a. Whether L1 contains all strings over the termainal vocabuary

b. Whether L1 is empty and regular

c. Whether L1 is infinite

d. Whether L2 is contained in L1

Choose your answer by clicking below.

Q156. Let L1={<M>| M is the encoding of a finite auotmaton} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a turing machine}. The following problems are decidable(choose the false statement)

a. Whether the complement of L1 contains w

b. Whether the complement of L1 is empty

c. Whether the complement of L1 is infinite

d. Whether L2 intersection L1 is empty

Choose your answer by clicking below.

Q157. Let L1={<M>| M is the encoding of a finite auotmaton} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a finite machine}. The following problems are decidable(choose the false statement)

a. Whether the complement of L1 contains w

b. Whether the complement of L1 is empty

c. Whether the complement of L1 is infinite

d. None of the above

Choose your answer by clicking below.

Q156. Let L1={<M>| M is the encoding of a dpda} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a dpda machine}. The following problems are decidable(choose the false statement)

a. Whether the complement of L1 contains w

b. Whether the complement of L1 is empty

c. Whether the complement of L1 is infinite

d. Whether L2 intersection L1 is infinite

Choose your answer by clicking below.

Q157. Let L1={<M>| M is the encoding of a dpda} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a dpda}. The following problems are decidable(choose the false statement)

a. Whether the complement of L1 contains w

b. Whether the complement of L1 is empty

c. Whether the complement of L1 is infinite

d. Whether L2 is contained in L1

Choose your answer by clicking below.

Q158. Let L1={<M>| M is the encoding of a dpda} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a dpda}. The following problems are decidable(choose the false statement)

a. Whether the complement of L1 contains w

b. Whether the complement of L1 is empty

c. Whether the complement of L1 is infinite

d. Whether L2 intersection L1 is empty

Choose your answer by clicking below.

Q159. Let L1={<M>| M is the encoding of a dpda} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a dpda}. The following problems are decidable(choose the false statement)

a. Whether the complement of L1 contains w

b. Whether the complement of L1 is empty

c. Whether the complement of L1 is infinite

d. Whether L2 intersection L1 is a dcfl

Choose your answer by clicking below.

Q160. Let L1={<M>| M is the encoding of a dpda} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a dpda}. The following problems are decidable(choose the false statement)

a. Whether the complement of L1 is contained in L2

b. Whether the complement of L1 is empty

c. Whether the complement of L1 is infinite

d. Whether L2 intersection L1 is a csl

Choose your answer by clicking below.

Q161. Let L1={<M>| M is the encoding of a pda} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a pda}. The following problems are decidable(choose the false statement)

a. Whether L1 contains w

b. Whether L1 is empty

c. Whether L1 is infinite

d. Whether L2 intersection L1 is empty

Choose your answer by clicking below.

Q162. Let L1={<M>| M is the encoding of a pda} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a pda}. The following problems are decidable(choose the false statement)

a. Whether L1 contains w

b. Whether L1 is empty

c. Whether L1 is infinite

d. Whether L2 contains all strings over the terminal vocabulary

Choose your answer by clicking below.

Q163. Let L1={<M>| M is the encoding of a pda} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a pda}. The following problems are decidable(choose the false statement)

a. Whether L1 contains w

b. Whether L1 is empty

c. Whether L1 is infinite

d. Whether L2 = L1

Choose your answer by clicking below.

Q164. Let L1={<M>| M is the encoding of a pda} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a pda}. The following problems are decidable(choose the false statement)

a. Whether L1 contains w

b. Whether L1 is empty

c. Whether L1 is infinite

d. Whether L2 is contained in L1

Choose your answer by clicking below.

Q165. Let L1={<M>| M is the encoding of a pda} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a finite automata}. The following problems are decidable(choose the false statement)

a. Whether L1 contains w

b. Whether L1 is empty

c. Whether L1 is infinite

d. Whether L2 = L1

Choose your answer by clicking below.

Q166. Let L1={<M>| M is the encoding of a pda} and w is a string in (0+1)*. Let L2={<M>| M is the encoding of a pda}. The following problems are decidable(choose the false statement)

a. Whether L1 contains w

b. Whether L1 is empty

c. Whether L1 is infinite

d. Whether L2 intersection L1 is empty

Choose your answer by clicking below.

Q167. Ram comes up with a universal language for cfls, Lucfl={<M,x>|M is the encoding of a pda that accepts w}. Choose the correct statement

a.Lucfl is a decidable language

b. Lucfl is partially decidable but not decidable

c.Lucfl is not partially decidable

d. Lucfl cannot exist

Choose your answer by clicking below.

Q168. Ram comes up with a universal language for dcfls, Ludcfl={<M,x>|M is the encoding of a dpda that accepts w}. Choose the correct statement

a.Ludcfl is a decidable language

b. Ludcfl is partially decidable but not decidable

c.Ludcfl is not partially decidable

d. Ludcfl cannot exist

Choose your answer by clicking below.

Q169. Ram comes up with a universal language for labas, Lulba={<M,x>|M is the encoding of a lba that accepts w}. Choose the correct statement

a.Lulba is a decidable language

b. Lulba is partially decidable but not decidable

c.Lulba is not partially decidable

d. Lulba cannot exist

Choose your answer by clicking below.

Q170. Ram comes up with a universal language for turing machines, Lu={<M,x>|M is the encoding of a turing that accepts w}. Choose the correct statement

a.Lu is a decidable language

b. Lul is partially decidable but not decidable

c.Lul is not partially decidable

d. Lul cannot exist

Choose your answer by clicking below.

Q171. Ram comes up with a universal language for halting turing machines, Lu={<M,x>|M is the encoding of a halting turing machine that accepts w}. Choose the correct statement

a.Lu is a decidable language

b. Lu is partially decidable but not decidable

c.Lu is not partially decidable

d. Lu cannot exist

Choose your answer by clicking below.

Q172. Let L0={<M,w,0>| M is the encoding of a pda that halts on input w} and let L1={<M,x,1>| M is the encoding of a pda that does not halt on input w}

Define a language L=L0UL1.

What can be said about L?

a. L is decidable

b. L is partially decidable but not decidable

c. L is not partially decidable

d. L is accepted by a pda

Choose your answer by clicking below.

Q173. Let L0={<M,w,0>| M is the encoding of a lba that halts on input w} and let L1={<M,x,1>| M is the encoding of a lba that does not halt on input w}

Define a language L=L0UL1.

What can be said about L?

a. L is decidable

b. L is partially decidable but not decidable

c. L is not partially decidable

d. L is accepted by a pda

Choose your answer by clicking below.

Q174. The following problems of csls are decidable

a. the equivalence problem

b.the containment problem

c. the membership problem

d. the completeness problem

Choose your answer by clicking below.

Q175.The following problems of csls are decidable

a. the emptiness problem

b.the finiteness problem

c. the infiniteness problem

d. whether the intersection of two csls is a csl

Choose your answer by clicking below.

Q176. The following problems of csls are decidable

a. the equivalence problem

b. whether the intersection of two csls is empty

c. the regularity problem

d. whether the complement of a csl is a recursive set

Choose your answer by clicking below.

Q177. The following problems of recursive sets are decidable

a. the membership problem

b. the emptiness problem

c.the completeness problem

d. the finiteness problem

Choose your answer by clicking below.

Q178. The following problems of recursive sets are decidable

a. the infiniteness problem

b. the equivalence problem

c. the containment problem

d.whether the complement is recursive

Choose your answer by clicking below.

Q179. The following problems of recursive sets are decidable

a. whether the recursive language is equal to a regular set R

b. the regularity problem

c. the equivalence problem

d. the completeness problem

Choose your answer by clicking below.

Q180. The following problems of recursive sets are decidable

a. the halting problem

b. the equivalence to a given r.e. set

c. the equivalence to a given csl

d. the equivalence to a given cfl

Choose your answer by clicking below.

Q181. The following problems of r.e. sets are decidable

a. the membership problem

b. the emptiness problem

c.the finiteness problem

d. whether the intersection of two r.e. sets is a language of the same type

Choose your answer by clicking below.

Q182. The following problems of r.e. sets are decidable

a. the infiniteness problem

b.the equivalence problem

c. the containment problem

d. whether the union of two r.e. sets is of the same type

Choose your answer by clicking below.

Q183. The following problems of r.e. sets are decidable

a. whether the intersection of two r.e. sets is empty

b. whether the r.e. set is equivalent to a given regular set

c. whether the r.e. set is regular

d. whether the Kleene closure of a r.e. set is a r.e. set

Choose your answer by clicking below.

Q184. The following problems of r.e. sets are decidable

a. whether the complement of a r.e. set is r.e.

b.whether the r.e. set is a csl

c. whether the r.e. set is a cfl

d.whether the reversal of the r.e. set is r.e.

Choose your answer by clicking below.

Q185. Choose the correct statement.

The following problems are decidable

a. whether a regular set is finite

b. whether a cfl is regular

c. whether a csl is a cfl

d. whether a recursive set is a csl

Choose your answer by clicking below.

Q186. Choose the correct statement

The following problems are decidable

a. whether a dcfl is finite

b. whether a recursive set is a cfl

c. whether a r.e. set is a csl

d. whether a r.e. set is a dcfl

Choose your answer by clicking below.

Q187. The following problems are decidable

Choose the correct statement

a. whether a dcfl is r.e.

b. whether a recursive set is regular

c. whether a recursive set if regular but not infinite

d. whether a r.e. set is a dcfl that is infinite

Choose your answer by clicking below.

Q188. The following problems are NP-complete.(Choose the correct one).

a. 1SAT

b. 2SAT

c. 3SAT

d. hamiltonian circuit problem where the graph does not have more than 100^1000 nodes

Choose your answer by clicking below.

Q189. The following problems are not NP-complete. (Choose the correct one).

a. 0/1 knapsack problem

b. node cover problem with the graphs having more than 100^100 nodes

c.edge cover problem with graphs having edges more than 100^100 nodes

d. travelling salesman problem with the number of nodes in the graph restricted to 100^100 nodes

Choose your answer by clicking below.

Q190. The following problems are not NP-complete.(Choose the correct one).

a. the partition problem

b. the chromatic number problem

c. the integer programming problem

d. the all pairs shortest path problem

Choose your answer by clicking below.

Q191. Choose the false statement

The following can be effectively enumerated

a. finite automata

b.deterministic push down automata

c. push down automata

d. halting turing machines

Choose your answer by clicking below.

Q192. Choose the false statement

The following can be effectively enumerated

a. deterministic linear bounded automata

b. linear bounded automata

c.halting turing machines

d. turing machines

Choose your answer by clicking below.

Q193. choose the false statement

The following can be effectively enumerated

a. multidimensional turing machines

b. multitrack turing machines

c. multiheaded turing machines

d. halting turing machines

Choose your answer by clicking below.

Q194. Choose the false statement

The following can be effectively enumerated

a. finite sets

b. regular sets

c. dcfls

d. recursive sets

Choose your answer by clicking below.

Q195. Choose the false statement

The following can be effectively enumerated

a. cfls

b.csls

c. recursive sets

d. r.e. sets

Choose your answer by clicking below.

Q196. Choose the false statement

The following can be effectively enumerated

a. type-0 grammars

b. halting turing machines

c. type-1 grammars

d. type 2 grammars

Choose your answer by clicking below.

Q197. Choose the false statement

The following can be effectively enumerated

a. type-0 grammars

b. halting turing machines

c. type-1 grammars

d. type 3 grammars

Choose your answer by clicking below.

Q198. Ram and Shyam define universal languages as follows

L0={<M,x,1>|M is the encoding of a turing machine that accepts x}

L00={<M,x,1>|M is the encoding of a halting turing machine that accepts x}

L1={<M,x,1>| M is the encoding of a linear bounded automata that accepts x}

L2={<M,x,1>| M is the encoding of a push down automata that accepts x}

L22={<M,x,1>| M is the encoding of a dpda that accepts x}

L3={<M,x,1>| M is the encoding of a fa that accepts x}

Choose the correct statement

a. all the universal languages are r.e.

b. the complements of all the universal languages are r.e.

c. all the universal languages are recursive

d. except L00 all the universal languages are r.e.

Choose your answer by clicking below.

Q199. Ram and Shyam define universal languages as follows

L0={<M,x,1>|M is the encoding of a turing machine that accepts x}

L00={<M,x,1>|M is the encoding of a halting turing machine that accepts x}

L1={<M,x,1>| M is the encoding of a linear bounded automata that accepts x}

L2={<M,x,1>| M is the encoding of a push down automata that accepts x}

L22={<M,x,1>| M is the encoding of a dpda that accepts x}

L3={<M,x,1>| M is the encoding of a fa that accepts x}

Choose the correct statement

a. all the universal languages are recursive.

b. the complements of all the universal languages are recursive

c. all the universal languages are r.e.

d. except L00 all the universal languages are r.e.

Choose your answer by clicking below.

Q200. Ram and Shyam define universal languages as follows

L0={<G,x,1>|G is the encoding of a type 0 that generates x}

L00={<G,x,1>|G is the encoding of a type 0 grammar that generates a recursive set and generates x}

L1={<G,x,1>| G is the encoding of a type 1 grammar that generates x}

L2={<G,x,1>| G is the encoding of a type 2 grammar that generates x}

L22={<G,x,1>| G is the encoding of a LR(k) grammar that generates x}

L3={<G,x,1>| G is the encoding of a type 3 grammar that generates x}

Choose the correct statement

a. all the universal languages are r.e.

b. the complements of all the universal languages are r.e.

c. all the universal languages are recursive

d. except L00 all the universal languages are r.e.

Choose your answer by clicking below.

Q201. Consider turing machines as enumerators.

We define a language L=[<M>| M is the encoding a turing machine that enumerates the strings it accepts in lexicographic order}.

Choose the correct statement.

a. L is a csl

b. L is recursive

c. L is r.e. and not recursive

d. L is not r.e.

Choose your answer by clicking below.

Q202.Ram and Shyam decide to classify a hierarchy of turing machines as follows:

L0={<M>|M is the encoding of turing machines that accept the recursive sets}

L1={<M>|M is the encoding of turing machines that accept the csls}

L2={<M>|M is the encoding of turing machines that accept the cfls}

L22={<M>|M is the encoding of turing machines that accept the dcfls}

L3={<M>|M is the encoding of turing machines that accept the regular sets}

L4={<M>|M is the encoding of turing machines that accept the finite sets}

Choose the correct statement

a. all the above languages are recursive

b. all the above languages are r.e.

c. all the above languages are not r.e.

d. all the above languages are r.e and not recursive

Choose your answer by clicking below.

Q203. The grammar

S---->aSbS|bSaS|e is

a. ambiguous

b. generates an inherently ambiguous language

c. is not ambiguous

d. generates an unequal number of a's and b's

Choose your answer by clicking below.

Q204. The grammar

S------>aSbS|bSaS|e i

a. generates an equal number of a's and b's

b. generates an unequal number of a's and b's

c. generates more a's than b's

d.generates more b's than a's

Choose your answer by clicking below.

Q205. The grammar

S--->aB|bA

A----->a|aS|bAA

B----->b|bS|aBB

a. is ambiguous

b. generates an inherently ambiguous language

c.is unambiguous

d. generates an unequal number of a's and b's

Choose your answer by clicking below.

Q206. The grammar

S--->aB|bA

A----->a|aS|bAA

B----->b|bS|aBB

a. generates an equal number of a's and b's

b. generates an inherently ambiguous language

c.generates more a's than b's

d. generates an unequal number of a's and b's

Choose your answer by clicking below.

Q207. The grammar

S--->aSBC|aBC

aB--->ab

bB---->bb

bC--->bc

cC---->cc

a. generates a regular set

b.generates a cfl

c. generates a dcfl

d. generates a csl

Choose your answer by clicking below.

Q208. The grammar

S--->aSBC|aBC

aB--->ab

bB---->bb

bC--->bc

cC---->cc

a. generates the set of all strings with an equal number of a's, b's and c's

b.generates {a^nb^n C^n|n>=1}l

c. generates more a's than b'sl

d. generates more b's than c's

Choose your answer by clicking below.

Q209. The grammar

S--->aSBC|aBC

aB--->ab

bB---->bb

bC--->bc

cC---->cc

a. is type-0 and not type-1

b.type-1 and not type-2

c. type-2 and not type-1l

d. type-3 and not type-2

Choose your answer by clicking below.

Q210. The grammar

S--->aSBC|aBC

aB--->ab

bB---->bb

bC--->bc

cC---->cc

a. is in CNF form

b.is in GNF form

c. generates a dcfl that is not regular

d. generates a csl that is not regular

Choose your answer by clicking below.

Q211. The grammar

S--->aSBC|aBC

aB--->ab

bB---->bb

bC--->bc

cC---->cc

generates a language that can be accepted by a

a. linear bounded automata

b.a push down automata

c. a deterministic push down automata

d. a finite automata

Choose your answer by clicking below.

Q212. Consider the following grammar

S---->bS|aA|b

A---->bA|aB

B--->bB|aS|a

Let Na(w) and Nb(w) denote the number of a's and b's in a string w. Then the language L(G) a subset of (a+b)+ generated by G is

A. {w| Na(w)>3Nb(w)}

B.{w|Nb(w)>3Na(w)}

C.{w|Na(w)=3k, k=0,1,2,...}

D.{w|Nb(w)=3k, k = 0,1,2,...} [GATE 2004]

Choose your answer by clicking below.

Q213.. Consider the following grammar

S---->bS|aA|b

A---->bA|aB

B--->bB|aS|a

Let Na(w) and Nb(w) denote the number of a's and b's in a string w in the reversal of the language. Then the language reversal of L(G) a subset of (a+b)+ generated by G is

A. {w| Na(w)>3Nb(w)}

B.{w|Nb(w)>3Na(w)}

C.{w|Na(w)=3k, k=0,1,2,...}

D.{w|Nb(w)=3k, k = 0,1,2,...}

Choose your answer by clicking below.

Q214. Consider the following grammar

S---->Sb|Aa|b

A---->Ab|Ba

B--->Bb|Sa|a

Let Na(w) and Nb(w) denote the number of a's and b's in a string w. Then the language L(G) a subset of (a+b)+ generated by G is

A. {w| Na(w)>3Nb(w)}

B.{w|Nb(w)>3Na(w)}

C.{w|Na(w)=3k, k=0,1,2,...}

D.{w|Nb(w)=3k, k = 0,1,2,...}

Choose your answer by clicking below.

Q215. Consider the following grammar

S---->bS|aA|b

A---->bA|aB

B--->bB|aS|a

The language generated by the grammar is

a. r.e but not recursive

b. recursive but not csl

c.csl but not cfl

d. regular but not finite

Choose your answer by clicking below.

Q216. Consider the following grammar

S---->bS|aA|b

A---->bA|aB

B--->bB|aS|a

The grammar is

a. type-0 but not type-1

b. type-1 but not type-2

c. type-2 but not type-3

d. type-3

Choose your answer by clicking below.

Q217. Consider the grammar

S--->AS|AA

A--->aAb|ab

Let Na(w) and Nb(w) denote the number of a's and b's in a string w. Then the language L(G) a subset of (a+b)+ generated by G is

A. {w| Na(w)>Nb(w)}

B.{w|Nb(w)<Na(w)}

C.{w|Na(w)=Nb(W)}

D.{w|Nb(w)not related to Na(w)}

Choose your answer by clicking below.

Q218. Consider the grammar

S--->aSa|bSb|aa|bb

A. {w| Na(w)>Nb(w)}

B.{w|Nb(w)<Na(w)}

C.{w|Na(w)=Nb(W)}

D.{w|Nb(w)not related to Na(w)}

Choose your answer by clicking below.

Q219. Consider the grammar

S--->aSa|bSb|aSb|bSa|aa|ab|ba|bb

A. {w| Na(w)>Nb(w)}

B.{w|Nb(w)<Na(w)}

C.{w|Na(w)=Nb(W)}

D.{w|Nb(w)not related to Na(w)}

Choose your answer by clicking below.

Q220. Consider the grammar

S--->AB

A--->aAb|ab

B--->b|bB

A. {w| Na(w)>Nb(w)}

B.{w|Nb(w)<Na(w)}

C.{w|Na(w)=Nb(W)}

D.{w|Nb(w)not related to Na(w)}

Choose your answer by clicking below.

Q221. Consider the grammar

S--->ABABS|AB

A--->a|aA

B---->b|bB

A. {w| Na(w)>Nb(w)}

B.{w|Nb(w)<Na(w)}

C.{w|Na(w)=Nb(W)}

D.{w|Nb(w)not related to Na(w)}

Choose your answer by clicking below.

Q222.Consider the gramamar.

S--->aaASb|ab

A--->aAb|ab

A. {w| Na(w)>Nb(w)}

B.{w|Nb(w)<Na(w)}

C.{w|Na(w)=Nb(W)}

D.{w|Nb(w)not related to Na(w)}

Choose your answer by clicking below.

Q223. The language {a^n b^n c^n|n>1}

a. can be generated by a type 3 grammar

b. can be generated by an LR(k) grammar

c. can be generated by a type 2 grammar

d. can be generated by a type 1 grammar

Choose your answer by clicking below.

Q224. The language {a^i b^j c^k|i>j>k}

a. can be generated by a type 3 grammar

b. can be generated by an LR(k) grammar

c. can be generated by a type 2 grammar

d. can be generated by a type 1 grammar

Choose your answer by clicking below.

Q225. The language {a^i b^j c^k|k=min(i,j)}

a. can be generated by a type 3 grammar

b. can be generated by an LR(k) grammar

c. can be generated by a type 2 grammar

d. can be generated by a type 1 grammar

Choose your answer by clicking below.

Q226. The language {a^i b^j c^k|k=max(i,j)}

a. can be generated by a type 3 grammar

b. can be generated by an LR(k) grammar

c. can be generated by a type 2 grammar

d. can be generated by a type 1 grammar

Choose your answer by clicking below.

Q227. The language {a^n^2|n>1}

a. can be generated by a type 3 grammar

b. can be generated by an LR(k) grammar

c. can be generated by a type 2 grammar

d. can be generated by a type 1 grammar

Choose your answer by clicking below.

Q228. The language {a^2^n|n>1}

a. can be generated by a type 3 grammar

b. can be generated by an LR(k) grammar

c. can be generated by a type 2 grammar

d. can be generated by a type 1 grammar

Choose your answer by clicking below.

Q229. The language {a^n|n>prime}

a. can be generated by a type 3 grammar

b. can be generated by an LR(k) grammar

c. can be generated by a type 2 grammar

d. can be generated by a type 1 grammar

Choose your answer by clicking below.

Q230. The language {a^n|n not prime}

a. can be generated by a type 3 grammar

b. can be generated by an LR(k) grammar

c. can be generated by a type 2 grammar

d. can be generated by a type 1 grammar

Choose your answer by clicking below.

Q231. The language {ww|w in (0+1)+}

a. can be generated by a type 3 grammar

b. can be generated by an LR(k) grammar

c. can be generated by a type 2 grammar

d. can be generated by a type 1 grammar

Choose your answer by clicking below.

Q232. The language {a^n!|n>1}

a. can be generated by a type 3 grammar

b. can be generated by an LR(k) grammar

c. can be generated by a type 2 grammar

d. can be generated by a type 1 grammar

Choose your answer by clicking below.

Q233. The language {a^i b^j c^k|i<>j and j<>k and k<>i}

a. can be generated by a type 3 grammar

b. can be generated by an LR(k) grammar

c. can be generated by a type 2 grammar

d. can be generated by a type 1 grammar

Choose your answer by clicking below.

Q234. The language {a^i b^j c^k|i=j or j=k or k=i}

a. can be generated by a type 3 grammar

b. can be generated by an LR(k) grammar

c. cannot be generated by a type 2 grammar

d. can be generated by a type 1 grammar

Choose your answer by clicking below.