## MCQs TOC|UGC-NET|GATE|Computer Science

11. | A Context free Grammar is ambiguous if |

A. | The grammar contains useless non-terminals. |

B. | It Produces more than one parse tree for some sentence. |

C. | Some production has two non-terminals side by side on the right hand side. |

D. | None of the Above. |

View/Hide Ans | |

Explanation | |

12. | CFLs and regular languages are both closed under the operations of |

A. | Union |

B. | Intersection |

C. | Complementation |

D. | Concatenation |

View/Hide Ans | |

Explanation | |

13. | Which of the Following problems are undecidable ? |

A. | Membership problem in context free languages. |

B. | Whether a given context - free language is regular. |

C. | Whether a finite state automation halts on all inputs. |

D. | Membership problem for Type 0 languages. |

View/Hide Ans | |

Explanation | |

14. | Recursive languages are : |

A. | A proper superset of context free languages. |

B. | Always recognizable by pushdown automata. |

C. | Also called Type 0 languages. |

D. | Recognizable by Turing Machines. |

View/Hide Ans | |

Explanation | |

15. | It is undecidable whether |

A. | An arbitrary Turing machine halts after ten steps. |

B. | A Turing machine prints a specific letter. |

C. | A Turing machine computes the product of two numbers. |

D. | None of the above. |

View/Hide Ans | |

Explanation | |

107. | Automaton accepting the regular expression of any number of a ' s is: |

A. | a* |

B. | ab* |

C. | (a/b)* |

D. | a*b*c |

View/Hide Ans | |

Explanation | |

108. | Grammars that can be translated to DFAs: |

A. | Left linear grammar |

B. | Right linear grammar |

C. | Generic grammar |

D. | All of these |

View/Hide Ans | |

Explanation | |

109. | The language accepted by a Push down Automata: |

A. | Type0 |

B. | Type1 |

C. | Type2 |

D. | Type3 |

View/Hide Ans | |

Explanation | |

110. | Given the following statements : (i) Recursive enumerable sets are closed under complementation. (ii) Recursive sets are closed under complementation. Which is/are the correct statements ? |

A. | only (i) |

B. | only (ii) |

C. | both (i) and (ii) |

D. | neither (i) nor (ii) |

View/Hide Ans | |

Explanation | |

111. | Q. Assume statements S1 and S2 defined as : S1 : L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively. S2 : The set of all Turing machines is countable. Which of the following is true ? |

A. | S1 is correct and S2 is not correct. |

B. | Both S1 and S2 are correct. |

C. | Both S1 and S2 are not correct. |

D. | S1 is not correct and S2 is correct. |

View/Hide Ans | |

Explanation |

Author Does Not claim of any answer these answers are as per expert opinion