THEORY OF COMPUTATION
|
|
Q1. 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]
Q2. 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
Q3. 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
Q4. 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
Q5. 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
Q6. 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
Q7. 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
Q8. 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
Q9. 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
|
-------------
For More Sample Papers Visit:
http://onestopgate.com/gate-preparation/ - http://onestopgate.com/gate-preparation/
|