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

1. | Assume the statements S1 and S2 given as : S1 : Given a context free grammarG, there exists an algorithm for determining whether L(G) is infinite. S2 : There exists an algorithm to determine whether two context free grammars generate the same language. 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 | |

2. | The number of eight-bit strings beginning with either 111 or 101 is ______. |

A. | 64 |

B. | 128 |

C. | 265 |

D. | None of the above |

View/Hide Ans | |

Explanation | |

3. | Which of the following conversion is not possible (algorithmically)? |

A. | regular grammar to context-free grammar |

B. | nondeterministic FSA to deterministic FSA |

C. | nondeterministic PDA to deterministic PDA |

D. | nondeterministic TM to deterministic TM |

View/Hide Ans | |

Explanation | |

4. | Regular expression for the language L = { w ∈ {0, 1}* | w has no pair of consecutive zeros} is |

A. | (1 + 010)* |

B. | (01 + 10)* |

C. | (1 + 010)* (0 + λ) |

D. | (1 + 01)* (0 + λ) |

View/Hide Ans | |

Explanation | |

5. | Recursively enumerable languages are not closed under: |

A. | Union |

B. | Intersection |

C. | Complementation |

D. | Concatenation |

View/Hide Ans | |

Explanation | |

6. | Grammar that produce more than one Parse tree for same sentence is: |

A. | Ambiguous |

B. | Unambiguous |

C. | Complementation |

D. | Concatenation Intersection |

View/Hide Ans | |

Explanation | |

7. | The finite automata accept the following language: |

A. | context free language |

B. | regular language |

C. | context sensitive language |

D. | all of the above |

View/Hide Ans | |

Explanation | |

8. | Write regular expression to denote a language L which accepts all the strings which begin or end with either 00 or 11 |

A. | [(00(0+1)* 11] + [11( 0 + 1)* 00] |

B. | [(00+11) (0+1)+] + [( 0 + 1)+ (00+11)]. |

C. | [(00+11) (0+1)*] + [( 0 + 1)* (00+11)] |

D. | (00+11) (0+1)* (00+11). |

View/Hide Ans | |

Explanation | |

9. | Write the regular expression to denote the language L over ? ={ a,b} such that all the string do not contain the substring “ ab”. |

A. | a*b* |

B. | b*a* |

C. | (ab)* |

D. | (ba)* |

View/Hide Ans | |

Explanation | |

10. | Recognize the CFL for the given CFG. S-> aB| bA, A-> a|aS|bAA, B-> b|bS|aBB |

A. | strings contain equal number of a's and equal number of b's. |

B. | strings contain odd number of a's and odd number of b's. |

C. | strings contain odd number of a's and even number of b's. |

D. | strings contain even number of a's and even number of b's. |

View/Hide Ans | |

Explanation |

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