One Stop GATE Forum: GATE–Sample Questions-Theory of Computation

Message

   Que. 1      Context-free languages are closed under:
A         Union , intersection
B         Union , Kleene closure
C         Intersection, complement
D         Complement, Kleene Closure

Que. 2     Let L p be the set of all languages accepted by a PDA by final        
  state and L E the set of all languages accepted by empty stack.     
     Which of the following is true?
A         L D = L E
B         L D É L E
C         L D = L E
D         None of the above

Que. 3     A grammar that is both left and right recursive for anonterminal,     
 is
A         Ambiguous
B         Unambiguous
C         Information is not sufficient to decide whether it is ambiguous or  
 (D)None of the above
D         (C)Information is not sufficient to decide whether it is ambiguous or 
  None of the above

Que. 4      Let S and T be languages over S = {a, b} represented by the       regular expressions (a + b *) * and (a + b) *, respectively.       Which of the following is true? 
A         S Ì T
B         T Ì S
C         S = T
D         S Ç T = f

Que. 5     Let L denotes the language generated by the grammar S->0S0/00.       
Which of the following is true?
A         L = 0 +
B         L is regular but not 0 +
C         L is context free but not regular
D         L is not context free

Que. 6     Which of the following need not necessarily be saved on a context switch 
between processes?
A         General purpose registers
B         Translation look aside buffer
C         Program counter
D         All of the above

Que. 7     Given an arbitrary non-deterministic finite automaton (NFA) with     
  N states, the maximum number of states in an equivalent minimized   
   DFA is at least
A         N^2
B         2^N
C         2N
D         N!

Que. 8     Which one of the following regular expression over {1,1} denotes the set of all strings not containing 100 as a substring?
A         0*(1+0)*
B         0*1010*
C         0*101
D         0*(10+1)*

Que. 9     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. 10     Consider the following decision problems :  (PI) Does a given finite 
state machine accept a given string  (P2) Does a given context free grammar 
generate an infinite number of stings  Which of the following statements 
is true?
A         Both (PI) and (P2) are decidable
B         Neither (PI) nor (P2) are decidable
C         Only (PI) is decidable
D         Only (P2) is decidable

Que. 11     Given the following expression grammar: 
E->E * F | F+E | F 
F-> F-F | id 
Which of the following is true? 
A         * has higher precedence than +
B         - has higher precedence than *
C         + and - have same precedence
D         + has higher precedence than *

Que. 12     Consider the following two statements: 
S1: {(O^2n) |n>/=1} is a regu1ar language 
S2: {(O^m)(1^n)(O^m+n)|m>/=l and n>/=l} is a regu1ar language 
Which of the following statements is correct? 
A         Only S1 is correct
B         Only S2 is correct
C         Both S1 and S2 are correct
D         None of S1 andS2 is correct

Que. 13     Which of the following statements in true?
A         If a language is context free it can always be accepted by a deterministic 
push-down automaton
B         The union of two context free languages is context free
C         The intersection of two context free languages is context free
D         The complement of a context free language is context free

Que. 14     Which of the following statements is false?
A         An unambiguous grammar has same leftmost and rightmost derivation
B         An LL(1) parser is a top-down parser
C         LALR is more powerful than SLR
D         An ambiguous grammar can never be LR(k) for any k

Que. 15     Consider the following languages: 
L1={w w l w (belongs) to) {a,b}*} 
L2={ww^R | w (belongs) {a, b}*, w R is the reverse of w} 
L3 = { 0^2i | i is an integer} 
L4 = {[(O)^i]^2| i is an integer} 
Which of the languages are regular? 
A         Only L1 and L2
B         Only L2, L3, and L4
C         Only L3 and L4
D         Only L3

Que. 16     Context free language are closed under
A         union, intesection
B         union,kleene closure
C         intesection,complement
D         complement,kleene closure

Que. 17     Context free languages are
A         closed under union
B         closed under complementation
C         closed under intersection
D         all of the above

Que. 18     Which one is equivalent   (i) (00)*(e+0)   (ii) (00)*   (iii) 0*   (iv) 
0(00)*
A         (i) and (ii)
B         (ii) and (iii)
C         (i) and (iii)
D         (iii) and (iv)

Que. 19     Type O grammer is
A         (C)both  and (b) above
B         (C)both (a) and  above
C         both (a) and (b) above
D         none of these

Que. 20      Consider a DFA over S = {a, b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?
A         8
B         14
C         15
D         48

Que. 21     The language L={(a^k)(b^k) | k>or= 1} is
A         type 3 grammer
B         type 2 grammer
C         type 1 grammer
D         type 0 grammer

Que. 22     Recursive languages are
A         a proper superset of context free languages
B         always recognizable by pushdown automata
C         also called type zero lanugages
D         all of these

Que. 23     A grammer that is both left and right recursive for a nopn-terminal is
A         ambiguous
B         unambiguous
C         information is not sufficient to decide whether it is ambiguous or 
unambiguous
D         none of the above

Que. 24     For what values of n is 10*n*log2 (n) >2*(n^2)?
A         only n>/= 32
B         only 0< font < ="20">
C         only 20
D         only n>/=0

Que. 25     Let * be defined as x*y = x' + y.Let z = x * y .Value of z*x is
A         x' + y
B         x
C         0
D         1

Que. 26     Which of the following regular expressions over {0,1} denotes the set of all strings not containing 
          100 as a substring
A         0*(1+0)*
B         0*1010*
C         0*1*01*
D         0*(10+1)*

Que. 27     Which of the following grammer rules violate the requirements of an operator 
grammer? P,Q,R are nonterminals and r,s,t are terminals.            (i) 
P -> Q R            (ii) P -> QsR            (iii) P -> e            (iv)P 
->Qtpr
A         (i) only
B         (i) and (iii) only
C         (ii) and (iii) only
D         (iii) and (iv) only

Que. 28     indicate which ofthe following statments are true      Recursive language 
are
A         A proper superset of context free languages
B         always recognizable by pushdown automata
C         recognizable by turing machine
D         also called type-0 languages

Que. 29     Which of the following is not decidable?
A         Given a  Turing machine M,a string s and an integer k,M accepts s 
within k steps
B         Equivalence of two given Turing machines
C         Language Accepted by a given finite state machine is not empty
D         language generated by a context free grammer is not empty

Que. 30     Regarding the power of recognition of languages,Which of the following 
statments is false?
A         the non-deterministic finite-state automata are equivalent to deterministic 
finite state automata.
B         non-deterministic push down automata are equivalent to deterministic 
push down automata.
C         non-deterministic Turing machines are equivalent to deterministic 
to  push down automata.
D         non-deterministic Turing machines are equivalent to deterministic 
Turing machines

Que. 31     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. 32     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. 33     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. 34     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. 35     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. 36     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. 37     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. 38     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. 39     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. 40     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
aparna Groupie Joined: 30Apr2007 Online Status: Offline Posts: 70	Topic: GATE–Sample Questions-Theory of Computation Posted: 27Nov2007 at 2:35am
	Que. 1 Context-free languages are closed under: A Union , intersection B Union , Kleene closure C Intersection, complement D Complement, Kleene Closure Que. 2 Let L p be the set of all languages accepted by a PDA by final state and L E the set of all languages accepted by empty stack. Which of the following is true? A L D = L E B L D É L E C L D = L E D None of the above Que. 3 A grammar that is both left and right recursive for anonterminal, is A Ambiguous B Unambiguous C Information is not sufficient to decide whether it is ambiguous or (D)None of the above D (C)Information is not sufficient to decide whether it is ambiguous or None of the above Que. 4 Let S and T be languages over S = {a, b} represented by the regular expressions (a + b ) and (a + b) , respectively. Which of the following is true? A S Ì T B T Ì S C S = T D S Ç T = f Que. 5 Let L denotes the language generated by the grammar S->0S0/00. Which of the following is true? A L = 0 + B L is regular but not 0 + C L is context free but not regular D L is not context free Que. 6 Which of the following need not necessarily be saved on a context switch between processes? A General purpose registers B Translation look aside buffer C Program counter D All of the above Que. 7 Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least A N^2 B 2^N C 2N D N! Que. 8 Which one of the following regular expression over {1,1} denotes the set of all strings not containing 100 as a substring? A 0(1+0)* B 01010 C 0101 D 0(10+1)* Que. 9 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. 10 Consider the following decision problems : (PI) Does a given finite state machine accept a given string (P2) Does a given context free grammar generate an infinite number of stings Which of the following statements is true? A Both (PI) and (P2) are decidable B Neither (PI) nor (P2) are decidable C Only (PI) is decidable D Only (P2) is decidable Que. 11 Given the following expression grammar: E->E * F \| F+E \| F F-> F-F \| id Which of the following is true? A * has higher precedence than + B - has higher precedence than * C + and - have same precedence D + has higher precedence than * Que. 12 Consider the following two statements: S1: {(O^2n) \|n>/=1} is a regu1ar language S2: {(O^m)(1^n)(O^m+n)\|m>/=l and n>/=l} is a regu1ar language Which of the following statements is correct? A Only S1 is correct B Only S2 is correct C Both S1 and S2 are correct D None of S1 andS2 is correct Que. 13 Which of the following statements in true? A If a language is context free it can always be accepted by a deterministic push-down automaton B The union of two context free languages is context free C The intersection of two context free languages is context free D The complement of a context free language is context free Que. 14 Which of the following statements is false? A An unambiguous grammar has same leftmost and rightmost derivation B An LL(1) parser is a top-down parser C LALR is more powerful than SLR D An ambiguous grammar can never be LR(k) for any k Que. 15 Consider the following languages: L1={w w l w (belongs) to) {a,b}} L2={ww^R \| w (belongs) {a, b}, w R is the reverse of w} L3 = { 0^2i \| i is an integer} L4 = {[(O)^i]^2\| i is an integer} Which of the languages are regular? A Only L1 and L2 B Only L2, L3, and L4 C Only L3 and L4 D Only L3 Que. 16 Context free language are closed under A union, intesection B union,kleene closure C intesection,complement D complement,kleene closure Que. 17 Context free languages are A closed under union B closed under complementation C closed under intersection D all of the above Que. 18 Which one is equivalent (i) (00)(e+0) (ii) (00) (iii) 0* (iv) 0(00)* A (i) and (ii) B (ii) and (iii) C (i) and (iii) D (iii) and (iv) Que. 19 Type O grammer is A (C)both and (b) above B (C)both (a) and above C both (a) and (b) above D none of these Que. 20 Consider a DFA over S = {a, b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have? A 8 B 14 C 15 D 48 Que. 21 The language L={(a^k)(b^k) \| k>or= 1} is A type 3 grammer B type 2 grammer C type 1 grammer D type 0 grammer Que. 22 Recursive languages are A a proper superset of context free languages B always recognizable by pushdown automata C also called type zero lanugages D all of these Que. 23 A grammer that is both left and right recursive for a nopn-terminal is A ambiguous B unambiguous C information is not sufficient to decide whether it is ambiguous or unambiguous D none of the above Que. 24 For what values of n is 10nlog2 (n) >2(n^2)? A only n>/= 32 B only 0< font < ="20"> C only 20 D only n>/=0 Que. 25 Let be defined as xy = x' + y.Let z = x y .Value of zx is A x' + y B x C 0 D 1 Que. 26 Which of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring A 0(1+0)* B 01010 C 0101* D 0(10+1) Que. 27 Which of the following grammer rules violate the requirements of an operator grammer? P,Q,R are nonterminals and r,s,t are terminals. (i) P -> Q R (ii) P -> QsR (iii) P -> e (iv)P ->Qtpr A (i) only B (i) and (iii) only C (ii) and (iii) only D (iii) and (iv) only Que. 28 indicate which ofthe following statments are true Recursive language are A A proper superset of context free languages B always recognizable by pushdown automata C recognizable by turing machine D also called type-0 languages Que. 29 Which of the following is not decidable? A Given a Turing machine M,a string s and an integer k,M accepts s within k steps B Equivalence of two given Turing machines C Language Accepted by a given finite state machine is not empty D language generated by a context free grammer is not empty Que. 30 Regarding the power of recognition of languages,Which of the following statments is false? A the non-deterministic finite-state automata are equivalent to deterministic finite state automata. B non-deterministic push down automata are equivalent to deterministic push down automata. C non-deterministic Turing machines are equivalent to deterministic to push down automata. D non-deterministic Turing machines are equivalent to deterministic Turing machines Que. 31 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. 32 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. 33 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. 34 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. 35 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. 36 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. 37 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. 38 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. 39 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. 40 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 Post Resume:* Click here to Upload your Resume & Apply for Jobs

	IP Logged


One Stop GATE Forum : GATE AT A GLANCE : Model Test Papers