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

Message

Que. 1      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. 2     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. 3     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. 4     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. 5     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. 6     Context free language are closed under
A         union, intesection
B         union,kleene closure
C         intesection,complement
D         complement,kleene closure

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

Que. 8     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. 9     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. 10      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

Author	Message
Arpita Groupie Joined: 04Jan2007 Online Status: Offline Posts: 73	Topic: Sample questions of Theory of Computation......... Posted: 13Feb2007 at 6:02pm
	Que. 1 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. 2 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. 3 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. 4 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. 5 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. 6 Context free language are closed under A union, intesection B union,kleene closure C intesection,complement D complement,kleene closure Que. 7 Context free languages are A closed under union B closed under complementation C closed under intersection D all of the above Que. 8 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. 9 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. 10 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
	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