One Stop GATE Forum: MODEL QUESTIONS OF THEORY OF COMPUTATION

Message

             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


One Stop GATE Forum : GATE Previous Years Test Papers - Discuss Here : IT Papers