One Stop GATE Forum: Sample questions of Theory of Computation.........

Message

 Que. 1      The string 1101 does not belong to the set represented by
A         110*(0+1)
B         1(0+1)*101
C         (10)*(01)*(00+11)*
D         (00+(11)*0)*

Que. 2     The following grammer   S->bS  S->b  S->aA  A->bA  A->aB  B->bB  B->aS 
B->a is
A         type 3 grammer
B         type 2 grammer
C         type 1 grammer
D         type 0 grammer

Que. 3     A language accepted by a pushdown Automaton in which the stack is limited 
to 10 items is best described as
A         Context free
B         Regular
C         Deterministic Context free
D         Recursive

Que. 4     Aliasing in the context of programming languages refers to
A         multiple variables having the same memory location
B         multiple variables having the same value
C         multiple variables having the same identifier
D         multiple uses of the same variable

Que. 5     If L1 is context free language and L2 is aregular language which ofthe 
followingi/are false
A         L1-L2 is not context free
B         L1 (intersection) L2 is  context free
C         ~L2 is context free
D         ~L1 isregular

Que. 6     consider the following regular expression :
R=(ab|abb)*bbab
Which of the following strings is NOT in the set denoted by R?
A         ababab
B         abbbab
C         abbabbbab
D         ababbabbbab

Que. 7     The following grammar  S->bS  S->b  S->aA  A->bA           is
A         type-3 grammer
B         type-2 grammer
C         type-1 grammer
D         type-0 grammer

Que. 8     The smallest finite aitomaton which accepts the language {x|length of x is divisible by 3} has 
A         2 states
B         3 states
C         4 states
D         5 states

Que. 9     The following production         A -> ab         A -> aA        aAb -> 
aBCb       is
A         type-3 grammer
B         type-2 grammer
C         type-1 grammer
D         type-0 grammer

Que. 10     Which of the following statment is false>
A         every finite subset of an non-regular set is regular
B         every subset of a regular set is regular
C         every finite subset of an regular set is regular
D         The intersection of two regular set is regular

Author	Message
Arpita Groupie Joined: 04Jan2007 Online Status: Offline Posts: 73	Topic: Sample questions of Theory of Computation......... Posted: 13Feb2007 at 6:07pm
	Que. 1 The string 1101 does not belong to the set represented by A 110(0+1) B 1(0+1)101 C (10)(01)(00+11)* D (00+(11)0) Que. 2 The following grammer S->bS S->b S->aA A->bA A->aB B->bB B->aS B->a is A type 3 grammer B type 2 grammer C type 1 grammer D type 0 grammer Que. 3 A language accepted by a pushdown Automaton in which the stack is limited to 10 items is best described as A Context free B Regular C Deterministic Context free D Recursive Que. 4 Aliasing in the context of programming languages refers to A multiple variables having the same memory location B multiple variables having the same value C multiple variables having the same identifier D multiple uses of the same variable Que. 5 If L1 is context free language and L2 is aregular language which ofthe followingi/are false A L1-L2 is not context free B L1 (intersection) L2 is context free C ~L2 is context free D ~L1 isregular Que. 6 consider the following regular expression : R=(ab\|abb)*bbab Which of the following strings is NOT in the set denoted by R? A ababab B abbbab C abbabbbab D ababbabbbab Que. 7 The following grammar S->bS S->b S->aA A->bA is A type-3 grammer B type-2 grammer C type-1 grammer D type-0 grammer Que. 8 The smallest finite aitomaton which accepts the language {x\|length of x is divisible by 3} has A 2 states B 3 states C 4 states D 5 states Que. 9 The following production A -> ab A -> aA aAb -> aBCb is A type-3 grammer B type-2 grammer C type-1 grammer D type-0 grammer Que. 10 Which of the following statment is false> A every finite subset of an non-regular set is regular B every subset of a regular set is regular C every finite subset of an regular set is regular D The intersection of two regular set is regular
	For more papers visit: http://onestopgate.com/gate-preparation/ Post Resume: Click here to Upload your Resume & Apply for Jobs

	IP Logged


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