McqMate

Q. |
## Given S = {a, b}, which one of the following sets is not countable? |

A. | the set all strings over Σ |

B. | the set of all language over Σ |

C. | the set of all binary strings |

D. | the set of all languages over Σ accepted by turing machines |

Answer» B. the set of all language over Σ |

772

0

Do you find this helpful?

9

View all MCQs in

Theory of ComputationNo comments yet

- The set which is not countable if we have ∑ = {a, b}, is
- Which of the following are regular sets?
- The regular sets are closed under:
- Which of the following are decidable? 1) Whether the intersection of two regular language is infinite. 2) Whether a given context free language is regular. 3) Whether two push down automata accept the same language. 4) Whether a given grammar is context free.
- State table of an FSM is given below. There are two states A And B, one input and one output. Let the initial state be A = 0 and B = 0. To take the machine to the state A = 0 and B = 1 with output = 1 the minimum length of input string required will be
- Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below: A B P - Q q R S r R S s R S The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
- 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?
- Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result)
- Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is 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?