• » When is the International Literacy Day observed every year? » 8th September
• » आयुष मंत्रालय ने व्यक्तिगत (अंतरराष्ट्रीय) श्रेणी में किसे 'प्रधानमंत्री योग पुरस्कार 2019' दिए जाने की घोषणा जून, 2019 में की- » अन्‍तोनिएता रोजी, इटली
• » वह अरब राष्ट्र जो की 'फाइनेंशियल एक्शन टास्क फोर्स' (FATF) की पूर्ण सदस्यता प्राप्त करने वाला पहला अरब देश जून, 2019 में बना- » सऊदी अरब
• » भारत ने किस देश को 3-1 से पराजित कर 'वुमेन एफआईएच सीरीज फाइनल हॉकी टूर्नामेंट' का खिताब 23 जून, 2019 को जीता? » जापान
• » भाजपा सांसद ओम बिरला राजस्थान के किस संसदीय क्षेत्र से सांसद चुने गए हैं; जिन्हें 17वीं लोकसभा का अध्यक्ष 19 जून, 2019 को चुना गया? » कोटा-बूंदी
If you find this context important and usefull. We request to all visitors to sheare this with your friends on social networking channels.

## GATE Exam Papers - (Computer Science ) - Part 1

 GATE Exam Papers - (Computer Science ) - Part 1GATE Exam Papers - (computer science ) - Part 1 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 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

## Tags

#

14 Aug, 2020, 16:12:12 PM