Active TopicsActive Topics  Display List of Forum MembersMemberlist  CalendarCalendar  Search The ForumSearch  HelpHelp
  RegisterRegister  LoginLogin
 One Stop GATE ForumGATE Previous Years Test Papers - Discuss HereIT Papers
Message Icon Topic: MODEL QUESTIONS OF THEORY OF COMPUTATION Post Reply Post New Topic
Author Message
Priya
Groupie
Groupie


Joined: 04Jan2007
Online Status: Offline
Posts: 82
Quote Priya Replybullet Topic: MODEL QUESTIONS OF THEORY OF COMPUTATION
    Posted: 09Feb2007 at 5:15pm


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/



Post Resume: Click here to Upload your Resume & Apply for Jobs

IP IP Logged
Post Reply Post New Topic
Printable version Printable version

Forum Jump
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot delete your posts in this forum
You cannot edit your posts in this forum
You cannot create polls in this forum
You cannot vote in polls in this forum

GET LATEST FRESHERS JOBS IN YOUR MAIL





This page was generated in 3.883 seconds.
Vyom is an ISO 9001:2000 Certified Organization

© Vyom Technosoft Pvt. Ltd. All Rights Reserved.

Job Interview Questions | Girls Magazine | DLL, OCX File Errors | Freshers Jobs | Placement Papers | More Papers