Theory of Computation ( TOC ) --- I

Q.1.  Which machine reads input only once from left to right ?

1. DFA
2. PDA
3. Turing machine
4.  All of these

 Q.2.  Which machine is equivalent to unrestricted grammar ?

1. DFA
2. PDA
3. Turing machine
4.  NFA

 Q.3.  Which grammar always produce rightmost derivation ?

1. PDA
2. CFG
3. Regular Grammar 
4. None

Q.4. Regular language closed under ?

1. Difference
2. Union
3. Complement
4.  All of these

 Q.5.  Which model has bounded tape ?

1. PDA
2. DFA
3. Linear Bounded automaton
4.  NFA

 Q.6.  Which problem is  undecidable ?

1. DFA minimization
2. CFG membership
3. Turing Machine Equivalence 
4. DFA equivalence

Q.7.  Which is not closed for CFL ?

1. Union
2. Concatenation 
3. Turing Machine Equivalence 
4. Complement

Q.8.  Which theorem proves regular languages cannot count ?

1. Rice theorem
2. Pumping lemma 
3. Myhill-Nerode theorem 
4. Church thesis

Q.9.  Which  problem is  decidable ?

1. GFG emptiness 
2. Halting problem
3. Post correspondence problem
4. TM Equivalence

Q.10.  Language accepted by deterministics PDA is ?

1. All CFL
2. Subset of CFL 
3. Regular Only 
4. Recursive languages
   
   

Answer Key: 

1. A
2. C
3. B
4. D
5. C
6. C
7. D
8. B
9. A
10. B