One Stop GATE Forum: THEORY OF COMPUTATION sample questions

Message


   
             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

			 
			 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

             
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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

			 
			 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


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