- Computer Science Engineering (CSE)
- Theory of Computation
- Unit 1
- Which of the statements is true:

Q. |
## Which of the statements is true: |

A. | The complement of a regular language is always regular. |

B. | Homomorphism of a regular language is always regular. |

C. | Both of the above are true statements |

D. | None of the above |

Answer» C. Both of the above are true statements |

View all MCQs in:
Theory of Computation

- Consider the following statements about the context free grammar G = {S - >SS,S - >ab,S ->ba, S - ε} I. G is ambiguous II. G produces all strings with equal number of a’s and b’s III. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G?
- Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?
- Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
- Consider the following statements I. Recursive languages are closed under complementation II. Recursively enumerable languages are closed under union III. Recursively enumerable languages are closed under complementation Which of the above statement are TRUE?
- Let S be an NP-complete problem, Q and R be two other problems not known to be in NP. Q is polynomial-time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
- For s Є (0+1)* let d(s) denote the decimal value of s(e.g.d(101)) = 5 Let L = {s Є (0+1)* d(s) mod 5=2 and d(s) mod 7 != 4} Which one of the following statements is true?
- Which of the following statements are TRUE? (1) The problem of determining whether there exists a cycle in an undirected graph is in P. (2) The problem of determining whether there exists a cycle in an undirected graph is in NP. (3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
- Which of the following statements is wrong?
- Consider the following problem x. Given a Turing machine M over the input alphabet Σ, any state q of M. And a word w Є Σ*, does the computation of M on w visit the state q? Which of the following statements about x is correct?
- Which of the following statements is/are FALSE? (1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. (2) Turing recognizable languages are closed under union and complementation. (3) Turing decidable languages are closed under intersection and complementation (4) Turing recognizable languages are closed under union and intersection.

Login to Continue

It will take less than 2 minutes

Report MCQ