Print Page | Close Window

Theory Of Computation(latest Question) Printed From: One Stop GATE Category: GATE Previous Years Test Papers - Discuss Here Forum Name: CS Papers Forum Discription: Computer Science Previous Year GATE Papers to can discussed here. URL: http://forum.onestopgate.com/forum_posts.asp?TID=3 Printed Date: 07Feb2025 at 2:23am Topic: Theory Of Computation(latest Question) Posted By: Reyan Tailer Subject: Theory Of Computation(latest Question) Date Posted: 27Dec2006 at 12:26pm Q1.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 Q2. 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 Q3. 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 Q4. 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 Q5. 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 Q6. 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 Q7.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 Q8. 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 Q9. 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 Q10. 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

Print Page | Close Window