- Computer Science Engineering (CSE)
- Theory of Computation
- Unit 1
- Any given transition graph has an equiva...

Q. |
## Any given transition graph has an equivalent: |

A. | regular |

B. | DFSM (Deterministic Finite State Machine) |

C. | NDFSM |

D. | All of them |

Answer» D. All of them |

View all MCQs in:
Theory of Computation

- 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 a graph G = (V, E) where I V I is divisible by 3. The problem of finding a Hamiltonian cycle in a graph is denoted by SHAM3 and the problem of determining if a Hamiltonian cycle exits in such graph is denoted by DHAM3. The option, which holds true, is
- Let FHAM be the problem of finding a Hamiltonian cycle in a graph G and DHAM be the problem of determining if a Hamiltonial cycle exists in a graph. Which one of the following 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.
- The regular expression have all strings in which any number of 0’s is followed by any number of 1’s followed by any number of 2’s is :
- Given an arbitrary non-deterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least:
- A spanning tree for a simple graph of order 24 has
- A Hamiltonian cycle in a Hamiltonian graph of order 24 has
- The minimum state automaton equivalent to the above FSA has the following number of states
- We think of a Turing machine’s transition function as a

Login to Continue

It will take less than 2 minutes

Report MCQ