One Stop GATE Forum: THEORY OF COMPUTATION SAMPLE QUESTIONS............

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

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

Author	Message
Arpita Groupie Joined: 04Jan2007 Online Status: Offline Posts: 73	Topic: THEORY OF COMPUTATION SAMPLE QUESTIONS............ Posted: 13Feb2007 at 5:57pm
	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 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
	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