THEORY OF COMPUTATION
Q1. Choose the correct statement.
The set of all strings over an alphabet S ={0,1} with the concatenation operator for strings
a) does not form a group
b) forms a noncommutative group
c) does not have a right identity
d) forms a group if the empty string is removed from S *
Q2. Consider the set of all strings S * over an alphabet S ={a,b} with the concatenation operator for strings, and
a) the set does forms semigroup
b) the set does not form a group
c) the set has a left and right identity
d) the set forms a monoid
Q3. Consider the set of all strings S * over the alphabet S ={a,b,c,d,e} with the concatenation operator for strings.
a. the set has a right identity and forms a semigroup
b. the set has a left identity and forms a monoid
c. the set does not form a commutative group but has an identity
d. the set does not form a semigroup with identity
Q4. Nobody knows yet if P = NP. Consider the language L defined as follows:
L=()+1)* if P = NP
And
L=j otherwise
Which of the following statements is true?
a) L is recursive
b) L is recursively enumerable but not recursive
c) L is not recursively enumerable
d) Whether L is recursive or not will be known after we find out if P = NP
Q5. Consider the language defined as follows
L= {a^n b^n|n>=1} if P=NP
And
L={ww|w in (a+b)+} otherwise
Which of the following statements is true?
a) L is recursive but not context sensitive
b) L is context sensitive but not context free
c) L is context sensitive
d) What L is will be known after we resolve the P=NP question
Q6. Consider the language defined as follows
L=(0+1)* if the CSLs are closed under complement
And
L=(0*1)*0* if P=NP
And
L=(10*)1* if P is not the same as NP
Which of the following statements is true?
a) L is always a regular set
b) L does not exist
c) L is recursive but not a regular set
d) What L is will be known after the two open problems P = NP and the closure of CSLs under complement are resolved
Q7. Consider the language defined as follows
L=(0+1)* if man goes to Mars by 2020AD
And
L=0* if man never goes to the Mars
Which of the following is true?
a. L is context free language but not recursive
b. L is recursive
c. Whether L is recursive or not will be known in 2020AD
d. L is a r.e. set that is not regular
Q8. Given an arbitrary context free grammar G, we define L as below.
L=(0+1)* if G is ambiguous
And
L=j if G is not ambiguous
a. L is a context-free language
b. L is recursive but not r.e.
c. What L is depends on whether we can determine if G is ambiguous or not
d. What L is is undecidable
Q9. Given an arbitrary turing machine M and a string w we define L as below.
L=(0*1)*0* if M halts on w
And
L=(0*1*)* if M does not halt on w
a. The type of L is undecidable because of the halting problem
b. L is a context-sensitive language
c. L is recursively enumerable and not context-free
d. L is context sensitive and not regular
Q10. Consider the language L defined below
L=(0+1)* if P=NP
And
L=(a^nb^n|n>=1} otherwise
a. Whether L is a regular set that is not context-free will be known after we resolve the P=NP question.
b. Whether L is context-free but not regular will be known after we resolve the P=NP question
c. L is context-sensitive
d. L is not recursive
Q11. It is undecidable if two cfls L1 and L2 are equivalent. Consider two cfls L1 and L2 and a language defined as follows
L={a^nb^nc^n|n>=234} if L1=L2
And
L={a^nb^nc^nd^n|n>=678} otherwise
a. L is recursive
b. L is context-free
c. We can never say anything about L as it is undecidable
d. L is regular
Q12. At present it is not known if NP is closed under complementation.
Consider L defined as below
L={w wR w| w in (0+1+2)* and wR is the reverse of w} if NP is closed under complement
And
L = {a^nb^nc^nd^ne^n|n>=34567} otherwise
a) L is recursive
b) L is context-free and not context-sensitive
c) L is recursively enumerable but not recursive
d) We will be able to say something about L only after we resolve the NP complementation issue
Q14. Nobody knows if P=NP at present. Consider a language L as defined below
L=(0+1)* if satisfiability is in P
L=(0*1)0* if satisfiability is not in P
L=(1*0)1* if 3-sat is in P
L=(0*1*)* if 3-sat is not in P
L=(0*1*0*1*)* if 0/1 knapsack problem is in P
L=(1*0*1*0*)* if 0/1 knapsack problem is not in P
L=(0*(00)*(1*11*)*) * if max-clique problem is in P
L=(0*(00)*(1*11*)*) * if node-cover problem is not in P
L=(0*1*)****(010)* if edge-cover problem is not in P
L=(0* + 1* + (00)* + (11)*)*(0100101010)* if the chromatic problem is not in P
What can we say about the string 0000111100001111=x
a) x is always in L
b) whether x is in L or not will be known after we resolve P=NP
c) the definition of L is contradictory
d) x can never be in L
Q15. An arbitrary turing machine M will be given to you and we define a language L as follows
L=(0+00)* if M accepts at least one string
L=(0+00+000)* if M accepts at least two strings
L=(0+00+000+0000)* if M accepts at least three strings
———
———
L=(0+00+000+—+0^n) *if M accepts at least n-1 strings
Choose the correct statement.
a) We cannot say anything about L as the question of whether a turing machine accepts a string is undecidable
b) L is context-sensitive but not regular
c) L is context-free but not regular
d) L is not a finite set
Q16. We are given two context-free languages L1 and L2 and L defined as below
a) L=(0+1)* if L1=L2
b) L=((0+00+000)*(1+11+111)*)* if L1 is contained in L2
c) L=((0(10)*)*(1(01)*)* if L2 is contained in L1
d) L=(00+11+0+1)*(0+00+000)* if L1 and L2 are incomparable
a) As all the conditions relating to L1 and L2 are undecidable we cannot say anything about L
b) L is recursively enumerable
c) L is recursive but not context-sensitive
d) L is context-sensitive but not context-free
e) L is context-free but not regular
Q17. It is undecidable if an arbitrary cfl is inherently ambiguous. We are given a cfg G and the language L is defined as below
L= (0+1)*01(0+1)* U 1*0* if L(G) is inherently ambiguous
L=(0+1)*10(0+1)* U 0*1* if L(G) is not inherently ambiguous
Choose the incorrect statement
a) L is regular
b) L iscontext-free
c) L is context-sensitive
d) The above choices can be resolved only if we know if L(G) is inherently ambiguous or not
Q18. We are given an arbitrary turing machine M and define the language L as below
L=(0*+1*)* if M halts on blank tape
L=(0+1*)* if M ever prints a 1
L=(0*+1)* if M ever enters a designated state q
L=((0+1+00+11+000+111)+)* if M accepts an infinite set
L=0*(10*)* if M accepts a finite set
L=1*(01*)* if M accepts exactly 45 strings
Choose the correct statement with reference to the string x=00000111111000000111111
a) x is in L
b) x is not in L
c) we can never decide if x is in L as all the problems of the turing machine are undecidable
d) whether x is in L depends on the particular turing machine M
Q19. We are given a language L defined as follows
L=(0+1)* if the Hamiltonian circuit problem is in P
L=(0*1*+0)* if the Traveling salesman problem is not in P
L=(0*1*1)*0* if the bin packing problem is in P
a) the definition of L is contradictory
b) What L is will be known after we resolve the P=NP question
c) L if a finite set
d) The string 01010101001010110010101 is in L
Q20. The intersection of two cfls can simulate a turing machine computation. We are given two cfls L1 and L2 and define the language L as below
a) L=(00)* if the intersection of L1 and L2 is empty
b) L=((0(00)*)(0(00)*))* if L1 is regular
c) L=(00+0000+000000)* if L2 is not regular
d) L=(00)*+(0000)* if the complement of L1 is a cfl
a) L is a finite set
b) L is a regular set
c) L is undecidable
d) L is recursive but not context-free
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
Q22. 0^2^n|n>=1} is
A D V E R T I S E M E N T
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Q42. The language {a^i b^j c^k d^l| i= j or j=k} is
A D V E R T I S E M E N T
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
THEORY OF COMPUTATION
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
A D V E R T I S E M E N T
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
A D V E R T I S E M E N T
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
[GATE 2004]
Q102. The language {a0^n 1^n|n>=1} U{b0^n 1^2n|n>=1} is
A. regular
A D V E R T I S E M E N T
B.context-free but not regular
C. context-sensitive but not context-free
D. type0 but not context sensitive
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
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
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
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
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
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
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
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
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
Q113. Choose the false statement. The regular sets are closed under
A. intersection
B. union
C. complement
D. inverse substitution
Q114. Choose the false statement. The regular sets are closed under
A. MAX
B. MIN
C. INIT
D. inverse substitution
Q115. Choose the false statement. The regular sets are closed under
A. CYCLE
B. INTERLEAVING
C. REVERSAL
D. inverse substitution
Q116. Choose the false statement. The regular sets are closed under
A. intersection
B. SUBSTITUTION
C. complement
D. inverse substitution
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
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
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
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
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
A D V E R T I S E M E N T
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
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
Q124. The cfls are not closed under
A. MIN,MAX
B. union,Kleene closure, INIT
C. CYCLE
D. reversal
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
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
Q127. The cls are not closed under
A. union
B. intersection
C. substitution
D. quotient with a regular set
Q128. The recursive sets are not closed under
A. complementation
B. union
C. intersection
D. substitution
Q129. The recursivse sets are not closed under
A. homomorphism
B. e-free homomorphism
C. intersection
D. positive Kleene closure
Q130. The r.e. sets are not closed under
A. union
B. intersection
C. complement
D. reversal
Q131. The r.e. sets are not closed under
A. intersection
B. substitution
C. CYCLE
D. complement
Q132. 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
Q133. 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.
Q134. 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
Q135. The DCFLs are not clsoed under(choose the false statement)
A. union, substitution
B. MIN,MAX
C. intersection
D. inverse substitution
Q136. Choose the false statement. The following languages are closed under reversal
A. Regular
B. cfls
C.dcfls
D. recursive sets
Q137. Choose the false statement. The following languages are closed under reversal
A. r.e. sets
B. csls
C.dcfls
D. recursive sets
Q138. Choose the false statement. The following languages are closed under complement
A. regular sets
B. dcfls
C. cfls
D. recursive sets
Q139. Choose the false statement. The following languages are closed under complement
A. regualar sets
B. r.e. sets
C. dcfls
D. recursive sets
Q139. Choose the false statement. The following languages are closed under complement
A. regular sets
B. dcfls
C. finite sets
D. recursive sets
Q140. The following languages are closed under substitution(choose the false statement)
A. regular sets
B. dcfls
C. cfls
D. r.e. sets
Q141. The following languages are closed under substitution(choose the false statement)
A. regular sets
B. cfls
C. csls
D. recursive sets
A D V E R T I S E M E N T
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
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
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
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
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.
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.
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.
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.
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
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
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
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
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
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
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
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
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
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
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
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
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
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
A D V E R T I S E M E N T
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
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
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
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
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
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
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
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
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
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
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
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
Q174. The following problems of csls are decidable
a. the equivalence problem
b.the containment problem
c. the membership problem
d. the completeness problem
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
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
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
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
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
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
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
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
A D V E R T I S E M E N T
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
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.
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
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
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
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
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
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
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
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
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
Q194. Choose the false statement
The following can be effectively enumerated
a. finite sets
b. regular sets
c. dcfls
d. recursive sets
Q195. Choose the false statement
The following can be effectively enumerated
a. cfls
b.csls
c. recursive sets
d. r.e. sets
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
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
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.
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.
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.
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.
A D V E R T I S E M E N T
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
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
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
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
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
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
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
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
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
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
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]
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,…}
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,…}
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
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
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)}
Q218. Consider the grammar
S—>aSa|bSb|aa|bb
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)}
Q219. Consider the grammar
S—>aSa|bSb|aSb|bSa|aa|ab|ba|bb
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)}
Q220. Consider the grammar
S—>AB
A—>aAb|ab
B—>b|bB
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)}
Q221. Consider the grammar
S—>ABABS|AB
A—>a|aA
B—->b|bB
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)}
A D V E R T I S E M E N T
Q222.Consider the gramamar.
S—>aaASb|ab
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)}
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
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
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
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
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
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
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
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
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
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
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
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
Tags: Exam, GATE, Interview, math, paper, Question
